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

Открыта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кэт8 уровень, Санкт-Петербург

вчера, 19:25

Время для 10 тысяч вставок Запускаю списки и разные числа выходят почему? 10 и 5 8 и 2

Сергей8 уровень, Санкт-Петербург

вчера, 18:33

Думал думал, пытал мозг, пытал, допер - неправильно располагал время (например timeA- timeB вместо timeB - timeA)

Денис9 уровень, Москва

17 июня, 11:50

Подскажите, пожалуйста, почему:

Integer a = 127, b = 127;
System.out.println( a == b);

Выводит в консоль true , но

Integer a = 128, b = 128;
System.out.println(a == b);

Выводит false Буду очень благодарен за доступный и содержательный ответ!

Сергей12 уровень, Москва

17 июня, 14:11

Мне помогло разобраться это объяснение: stackoverflow

Денис9 уровень, Москва

18 июня, 14:39

мне нет D: "Класс Integer содержит кэш обёрток" - что это значит?

Сергей12 уровень, Москва

18 июня, 16:22

Внутри класса Integer есть статический вложенный класс IntegerCache, который содержит массив( с названием "cache" - кэш) для объектов типа Integer(оберток для примитива int). При первом использовании в коде твоей программы класса Integer этот массив автоматически заполняется объектами типа Integer со значениями от -128 до 127. При объявлении новой переменной типа Integer и автоупаковке в неё значения от -128 до 127, переменная получает ссылку на уже готовый, созданный ранее объект в кэше с соответствующим значением. То есть, в первом случае, обе переменные a и b из твоего примера будут содержать ссылку на один и тот же объект Integer в кэше со значением 127. Так как оператор == сравнивает ссылки, он выдаст true. Во втором случае, так как в кэше объекта Integer со значением 128 нет, каждый раз для a и b создаются новые объекты, и ссылки на них различаются. Знающие, поправьте, если я что-то не так понял) Вот ещё хорошая инфа про кэш, автоупаковку и т.п.

Руслан8 уровень, Москва

суббота, 18:01

Я тоже забыл про это. Так как у нас в списке объекты Integer, то их сравнивать нужно не через (a == b), а через (a.equals(b)). В первом случае идет сравнение ссылок на объекты, а не значений. В лекциях это было.

Alexander Morkvashyov8 уровень, Самара

13 июня, 15:53

холи щет я её решил!!11

Евгений9 уровень

12 июня, 13:56

Очень не нравится этот уровень. Вообще нет понимания зачем нам дали коллекции сейчас!

Olga Enaldieva15 уровень

4 июня, 07:54

Удивительно, но даже последняя задача показалась мне ооочень легкой. Кстати, только сейчас понял, для чего были нужны джинерики.

Dmitry Potamoshnev19 уровень, Москва

5 июня, 18:50

все относительно :) Мне понравилось, что наконец-то мозг пришлось чуть-чуть включить, т.к. остальные задачки совсем унылая тоска)

Sergey Rudeshko9 уровень, Москва

28 мая, 11:35

последняя задача понервничала меня

Алексей9 уровень, Санкт-Петербург

21 мая, 19:05

капец насколько большая разница в производительности разных операций для разных списков!

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

3 мая, 20:45

Может кому пригодится для обхода 127 false == (arrayList.get(i).equals(arrayList.get(i - 1)))

Евгений9 уровень

12 июня, 13:54

я в условии сравнения элементы насильно в long сделал. Тоже прошло.

Денис9 уровень, Москва

17 июня, 11:59

выше задал вопрос, почему два объекта(листы содержат объекты Integer а не int) до 127 сравниваются с помощью == правильно, а больше 128 сравниваются правильно только через метод equals. Интересно, все-таки, почему

Самуил Олегович18 уровень, Киев

2 мая, 22:11

368 ЧМ