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

Открыта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Dan Banan10 уровень, Великий Новгород

суббота, 21:27

Если что equals работает с Integer, может кому поможет. Я это подсмотрел в решениях. При решении же своей задачи до этого сам не дошел и изобрел велосипед с колесами из if-else

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

14 августа, 20:41

на последней задачке спас отладчик.. а все из за того что забыл кое что

Petr11 уровень, Сочи

14 августа, 12:06

Последнюю задачу валидатор не пропустил из-за двусвязного списка, заменил на ArrayList - и тестирование прошло успешно

Марат8 уровень, Penza

7 августа, 06:28

Это была очень непростая задачка)

Стас13 уровень, Пятигорск

30 июля, 13:54

Последняя задачка прикольная. ))) Пришлось подумать.

Светлана10 уровень

29 июля, 13:55

Объясните мне, пожалуйста, что это за оборот такой - "без нытья и катанья" в описании задачи "10 тысяч удалений и вставок".

LeonBBBBBB8 уровень, Екатеринбург

15 августа, 11:45

https://www.proza.ru/diary/cookin/2014-05-30

Светлана10 уровень

15 августа, 15:36

Так вот почитайте по этой ссылке, что это искаженный вариант существующей поговорки, который люди используют, когда не понимают смысла этой поговорки. И это надо учесть, если вы не хотите тоже производить впечатление людей, которые "слышали звон, да не знают, где он". Если вы понимаете, о чем я. :)

LeonBBBBBB8 уровень, Екатеринбург

понедельник, 16:52

так я про это же )

A-lw12 уровень, Омск

24 июля, 06:15

Время для 10 тысяч вставок. Результат 8 : 2. Если это одинаково "быстро", то страшно представить какова разница между "Быстро" и "Медленно"

A-lw12 уровень, Омск

24 июля, 06:20

~~Вопрос~~ снят. get = 1 : 78

Viktor Gromov11 уровень

24 июля, 08:51

Сначала хотел сделать поправку на миллисекунды, но потом решил поиграться со значениями. В общем, вот что получил: ArrayList / LinkedList add: 10.000 = 7 / 2 100.000 = 607 / 6 (~ 100 / 1) 1.000.000 = 60025 / 185 (~ 300 / 1) get: 10.000 = 1 / 87 100.000 = 3 / 857 (~ 1 / 280) 1.000.000 = 7 / 7110 (~1 / 1000) Кстати, тут уже можно даже почувствовать задержку. В случае с 1.000.000 add, у меня ноут начал активно охлаждаться и весь процесс для ArrayList занял около минуты (ну, собственно, это можно видеть). Не знаю, о каком равенстве тут говорится, т.к. она огромная при большом количестве операций, но на маленьких количествах очень похоже на правду. Если брать их отношения, то вполне все верно: 1/ 300 у add получается только при 1.000.000, тогда как с get мы это уже на 100.000 получаем. Однако, думаю, тут правильнее брать разницу. А разница огромная: в то время как get на 1M имеет разницу в 7 секунд, add уже расправляется с разницей в минуту. Почему они утверждают обратное, не понятно.

A-lw12 уровень, Омск

24 июля, 09:14

Я об этом же! Не понятно что автор имел в виду тогда, единственно, могу предположить, что это было сделано для симметричности таблички ))

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

8 августа, 20:19

Автор имел в виду добавление в конец списка, add без указания индекса, тогда для 1_000_000 = 482/ 830

Artem9 уровень

16 июля, 13:32

кто подскажет list.get(i).equals(list.get(i+1) в чем разница list.get(i)==(list.get(i+1)

Den Kiber13 уровень

18 июля, 13:45

Операция сравнения == применима только к примитивным типам переменных, такой оператор сравнивает между собой значения для примитивных типов или же ссылки на объект в случае, если в переменной хранится ссылка. http://java-online.ru/integer-cache.xhtml

Nadin9 уровень, Омск

8 июля, 06:08

Последнюю задачу пропустил вот с такой записью: List<Integer>list=new ArrayList<>(); В чем отличие от ArrayList<Integer>list=new ArrayList<>(); ???

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

8 июля, 10:12

почитайте про полиморфизм в Java и интерфейсы. думаю будет позже в лекциях.

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

26 июня, 19:25

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

Artificial Intelligence17 уровень, Москва

27 июня, 11:27

Потому что в main твой метод вызывается дважды: Сначала для ArrayList, Потом для LinkedList. На основе вывода делай выводы, какие списки для каких задач больше подходят.

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

4 июля, 18:49

Мне не понятно разница цифр при разных вызовах, то есть 10 и 8 для ArrayList? Почему не всегда 10

Alexey10 уровень, Екатеринбург

7 июля, 05:06

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

Ilya Ivanov20 уровень, Казань

13 июля, 19:59

в многопоточности узнаешь больше.