Задачи на измерение производительности списков

Открыта

— А вот и ты. Я уже начал скучать. Где это ты пропадал? Вот тебе задачи.

— Интересные?

— Ну конечно! Очень интересные:

Коллекции могут быть реализованы разными способами и нет единственного – самого правильного. При одном подходе одни операции являются быстрыми, а остальные медленными, при другом – все наоборот. Нет одного идеального, подходящего всем решения. Не будем мучится выбором и создадим сразу два списка — LinkedList и ArrayList.

Повторение однообразных действий без нытья и катанья — вот чем славны компьютеры, вот чего помогают избегать программисты простым смертным! Не будь средств автоматизации повторений, условие этой задачи звучало бы как приговор. А так вроде бы все нормально: для arrayList и linkedList провести 10 тысяч вставок, удалений, а также вызовов get и set.

Время — наш самый ценный ресурс. На всех планетах, за исключением Тральфамадора, над ним власти нет. Поэтому на Тральфамадоре нет программистов, а на Терре — их полно, потому что они помогают другим экономить свое время. Давайте измерим, сколько времени занимает 10 тысяч вставок для списков LinkedList и ArrayList и восхвалим автоматизацию.

Много ли времени и усилий вы готовы потратить, чтобы получить какое-либо благо? Думаем, достаточно, вы же пытаетесь стать программистом прямо сейчас? Давайте посмотрим, сколько времени занимает 10 тысяч вызовов get для списков LinkedList и ArrayList. Метод getGetTimeInMs должен вернуть время своего исполнения в миллисекундах.

В этой задаче мы работаем со списками LinkedList и ArrayList, и вот каким образом. Нам нужно реализовать 4 метода. Каждый из них должен возвращать список, который лучше всего подходит для выполнения данных операций (быстрее всего справится с большим количеством операций). А вот измерять ничего не нужно.

Если числа повторяются, значит, это кому-нибудь нужно? В данный момент это нужно нам, чтобы потренироваться решать задачи на списки. Давайте создадим список чисел и добавим в него 10 чисел с клавиатуры. Наша задача состоит в том, чтобы вывести на экран длину самой длинной последовательности повторяющихся чисел в списке.

Предыдущая лекция

Следующая лекция

Комментарии (364)

популярные
новые
старые

Для того, чтобы оставить комментарий вы должны авторизоваться

Сергей Цехмистренко9 уровень, Минск

29 марта, 15:18

Вот немного про кэширование Integer, если кому интересно)

Дмитрий19 уровень

20 марта, 20:14

В последнем задании не используйте LinkedList, с ним падает четвертый пункт ("Программа должна добавлять в коллекцию 10 чисел, согласно условию.").

Павел Михайлищев18 уровень, Krasnogorsk

8 марта, 19:56

Последняя задача оказалась легкой, долго забивал на нее но потом решил, правда видел подсказки про equals. Подскажите, а как сделать через "=="? Как привести к int?

Ксенія Українка10 уровень, Киев

26 марта, 09:59

Integer n; int n1 = (int) n;

Андрей8 уровень, Самара

суббота, 13:59

Почему бы сразу не объявить List<Integer> list = new ArrayList<>();

Romy8 уровень, Киев

3 марта, 16:53

Ну спасибо за эту подставу с .equals(); Начал писать на компьютере в vscode, закончил на телефоне в dcoder-e, никаких комментариев и обсуждений не смотрел, чтобы подсказок не увидеть, а вы вон как... драться каской?

Дмитрий Романюк14 уровень, Санкт-Петербург

30 января, 15:20

Для решения этой задачи будет полезна эта статья

Василий Бабин17 уровень, Москва

22 января, 14:26

Cамая длинная последовательность Код работает, но не проходит проверку!

list.get(i) == list.get(i+1)

Пишет ошибку: Убедитесь, что программа работает правильно, если последовательность состоит из чисел, которые больше 127. Хотя программа работает и с больше 127 и количества больше 127 (я проверил), а проверку не проходит. Да вообще что это значит?! Я почитал ниже, что надо использовать int или equals, а это не проходит:

list.get(i) == list.get(i+1)

Но почему прямое сравнение не проходит, думаю из-за оболочки Integer, так как это не простое int, а ссылка? И что это вообще за ошибка такая кто знает разъясните, пожалуйста.

Василий Бабин17 уровень, Москва

22 января, 14:52

Ответ нашёл в комментариях к задаче. Спасибо Vladislav Vasilyev! "При старте JVM, создается 128 экземпляров Integer для чисел от 0 до 127 включительно. При раcпаковке, если значение в диапазоне от 0 до 127, переменной присваивается сгенерированная при старте JVM ссылка на экземпляр Integer. Если же присваивается значение более 127, то генерируется новый класс и его ссылка присваивается переменной. Операция сравнения сравнивает только ссылки. Получается если число меньше 127, то ссылки ведут на один и тот же экземпляр Integer. Если больше 127, то ссылки ведут на разные экземпляры независимо от их значения. Поэтому сравнивать по значению надо всегда через equals(). или привести к (int)"

+13

Justinian41 уровень, Киев

26 января, 15:07

Количество экземпляров кешируемых объектов может отличаться в зависимости от реализации конкретной JVM или настроек запуска (верхняя граница может увеличиваться при помощи параметров запуска), но по умолчанию, как я понимаю это 256 экземпляров, в диапазоне от -128 до 127, причем поведение подобное идет для всех целочисленных типов - включая short, long, char.

Алексей13 уровень, Москва

21 января, 11:53

в задаче на самую длинную последовательность надо было указывать буквально размер последовательности, а не количество цифр в самой длинной последовательности. я час убил на то, чтобы написать это, а там все гораздо проще оказалось

Ксенія Українка10 уровень, Киев

26 марта, 10:02

? цифр или чисел?

Павел Андрусов23 уровень, Липецк

21 января, 07:24

в последней задаче криво поставлено условие насчет типа списка (точнее его вовсе нет). при использовании LinkedList ругается на 4 пункт - "Программа должна добавлять в коллекцию 10 чисел, согласно условию.", но не совсем ясно как это сваязано

Radik Gismatullin17 уровень, Казань

27 января, 16:33

Я сделал так:

List<Integer> list = new ArrayList<>();

Павел Андрусов23 уровень, Липецк

27 января, 17:05

ну мне тоже пришлось делать через ArrayList, LinkedList не принимал, хотя в ТЗ нет ничего на этот счет

Дмитрий Пищанецкий22 уровень, Днепр

12 февраля, 12:06

Тоже решил поставить LinkedList, хотя заметил, что в импортах уже добавлен ArrayList. Результат выдавался правильный, но ошибка проверки была аналогичная: "Программа должна добавлять в коллекцию 10 чисел, согласно условию." Пришлось в итоге на ArrayList поменять.

Irina16 уровень, Гродно

2 марта, 11:18

В предпоследней задаче нужно было выбрать лучший подходящий тип списка для выполнения конкретных операций, т.е. из предыдущей задачи мы должны вынести информацию, что для получения значений из списка больше подходит ArrayList. Поскольку в последней задаче нужно получать данные, то наиболее подходящий тип - ArrayList.

Павел Андрусов23 уровень, Липецк

2 марта, 21:17

мы тут говорим о последней задаче, по предпоследней вопросов нет

КАРАБАНЬ ГЛЕБ АЛЕКСАНДРОВИЧ 9 уровень, Москва

14 марта, 19:09

на сколько я понял, ответ был дан тоже по последней, в предпоследней мы узнали что для get нужно использовать ArrayList , потому в последней он и должен быть. Типо мы узнали что он лучше для данной операции. Правда сам бы до этого я не дошел

ram097331 уровень, Набережные Челны

1 января, 18:04

Заполнить лист тестовыми данными: List<Integer> list = new ArrayList<Integer>(Arrays.asList(1,1,1,4,4,4,4,4,4,4));

Евгений18 уровень, Москва

18 января, 16:06

это помогло проверить условие, когда самая длинная последовательность длится до конца List. и проверить после - текущий счетчик не больше ли максимума

Andrew Shemetov9 уровень, Ростов-на-Дону

14 декабря 2019, 21:21

Подскажите, пожалуйста, у меня в последней задаче Самая длинная последовательность есть ошибка: В методе main объяви переменную типа List с типом элементов Integer и сразу проинициализируй ee. В коде всё просто:

ArrayList<Integer> list = new ArrayList<Integer>();

Что у меня не так?

Andrew Shemetov9 уровень, Ростов-на-Дону

14 декабря 2019, 21:27

А что, так можно было? ))

List<Integer> list = new ArrayList<Integer>();

Тима35 уровень, Алматы

9 января, 05:42

Насколько я знаю, это и есть полиморфизм, вы работаете с несколькими типами так, будто это один тип, то есть указав для поля list тип List, вы можете присвоить ссылку на объект любого класса реализующего интерфейс List