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

Открыта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

вторник, 13:36

Странно что нет задач про котов

Sergey Neizhmakov8 уровень

4 октября, 19:30

Куда девается темная материя??? Почему она убывает???

Александр8 уровень, Пермь

5 октября, 10:28

Каждая лекция на 8-ом уровне стоит 8 ЧМ

Михаил Паскевич10 уровень, Киев

4 октября, 16:31

Если кому-то будет выдавать ошибку: проверить цифры больше 127. Почитайте про Integer пул(pool). Это к теме == и equals():

Alex9 уровень

6 октября, 08:52

спасибо дружище! пригодилось))

Никита Сергеев9 уровень

вчера, 12:08

Это ты так решил из далека зайти, что бы явно не намекнуть на решение проблемы?:)

Михаил Паскевич10 уровень, Киев

вчера, 15:53

Ну да, вроде в правилах просили не писать прямые ответы :)

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

2 октября, 10:37

Последнюю задачу решил через ListIterator. Перемудрил, можно было простым for. Зато стал лучше разбираться что это за зверь - итератор. Обо что сломал больше всего копий и что долго дебажил. Значение следующего элемента (nextElement) последовательности (sequence) стоит брать через

nextElement = sequence.get(iterator.nextIndex())

а не через

nextElement = iterator.next();

потому что курсор итератора в момент вызова iterator.next() смещается вправо и цикл ломается. Аналогично со значением предыдущего элемента (previousElement) последовательности:

previousElement = sequence.get(iterator.previousIndex());

а не

previousElement = iterator.previous();

потому что курсор в момент вызова iterator.previous() смещается влево и цикл закольцовывается на одной итерации и программа виснет.

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

26 сентября, 11:59

Квартет «Методы»: У меня во всех методах (add, get, set, remove) LinkdeList проигрывает ArrayList'у вчистую... И да, я понимаю, что валидатор по add'у и remove'у ждет выигрыша LinkedList'а. Но как?

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

26 сентября, 12:07

Мда, весь код теперь: - создание списка - return созданный список Критерий: предыдущая лекция =(

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

23 сентября, 07:53

была проблема , решил путем замены == на equals в условии

Андрей Ермоленко14 уровень

2 октября, 14:44

или сделать приведение к типу данных через (int)

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

18 сентября, 15:05

Ты не один во вселенной:)

Александр13 уровень

17 сентября, 17:32

Читаю комменты и чувствую себя дауном, у всех всё получается.

+21

Zaur12 уровень

17 сентября, 17:44

лайкнул, потому что не ты один такой

Dion9 уровень

27 сентября, 16:31

лайкнул потому что не вы одни такие))

Дмитрий Чесноков9 уровень, Санкт-Петербург

27 сентября, 20:48

лайкнул, потому что тоже так думаю)))

GrooveDevelop18 уровень, Керчь

11 сентября, 11:58

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

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

26 сентября, 14:00

действительно важно читать внимательно каждое слово. Тогда валидация быстрее пройдет)

Ruslan Repin15 уровень, Ейск

7 сентября, 17:30

Интересно, смотрю уровни у комментаторов растут.))

Алексей10 уровень, Полысаево

2 октября, 09:52

Учимся. Алексей, 8-й уровень.

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

вчера, 11:17

У вас за месяц плюс семь уровней )