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

Открыта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Nitrop8 уровень

30 января, 15:22

Я шото пропустил?Когда это тут начали применяться объекты типа Date?Я вот например сейчас много туплю,из-за того,что не знаком с Date.

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

30 января, 20:21

две лекции назад

Aleksei Dobrovolskii17 уровень

28 января, 07:39

Вот эта засада с 127, мне кажется, причина многих багов в конечном продукте у начинающих программистов)

Pavel10 уровень

18 января, 21:32

Почитал комментарии и чувствую себя дауном, но не от того что, что то не получилось , все так замудренно решают задачу на самую длинную последовательность, не все обьяснения даже понял. p.s. сам решил давольно быстро одним циклом , две переменных и два " if "

Вячеслав12 уровень, Москва

17 января, 12:46

Одним циклом решилась задача. Создал две переменные, инициировал единичками. Дальше в цикле проверял, равен ли текущий элемент следующему. Если равен, то (увеличиваем первую переменную, и если первая переменная больше второй, то делаю вторую равной первой). Ну а если не равен - то сбрасывал первую переменную. То есть фактически считал количество подряд идущих цифр, и если это количество больше максимума - то обновлял максимум. Без приведения типов

Дмитрий Ильин8 уровень, Москва

12 февраля, 10:28

тоже так сделал правда инициализировал нулями и ни каких проблем, просто видимо немного по разному все сделали, тоже читал что народ инициализировал единицами, зачем не понял :)

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

16 января, 14:27

Число решивших первые задачи было по 150 000. Сейчас уже около 40 000. Прямо на ходу народ отваливается %) Приятно быть крепким орешком.

Olga11 уровень

17 декабря 2018, 20:48

Задача решена была верно сразу. Протестировала несколько раз. Но валидацию прошла с 4 попытки. В чем была проблема. При решении использовались два ArrayList. Один - для добавления последовательности, второй - для списка длин повторяющихся последовательностей, из которого потом находили максимальное число (возможно, есть способы решения лучше, но на данном уровне я решила задачу именно так). Если объявить оба ArrayList подряд, то при валидации выдается ошибка "Программа должна добавлять в коллекцию 10 чисел, согласно условию." Остальные пункты - всё верно. А если объявить первый ArrayList и сразу добавить в него 10 чисел, а потом уже второй ArrayList, то всё ок. Как-то так. Искала ошибку, которой нет.

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

7 февраля, 14:30

это да... А мне пришлось вместо второго ArrayList делать массив, что обойти валидатор :)

Игорь22 уровень, Нижний Новгород

14 декабря 2018, 22:27

Тем, кто столкнулся с ошибкой при числах больше 127, есть хорошая подсказка здесь: Сравнение объектов: практика, раздел "Java 5.0. Autoboxing/Unboxing: '==', '>=' и '<=' для объектных оболочек." Хорошо применим совет, который дан в конце этого раздела: "если есть возможность обойтись без autoboxing/unboxing, то стоит эту возможность использовать на полную катушку"

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

30 января, 22:41

Спасибо

Артем Малаховский9 уровень, Минск

10 февраля, 19:30

спасибо

Вадим20 уровень, Одесса

14 декабря 2018, 22:23

полезное задание, дало по мозгам что плохо об Integer читал :)

Juris 8 уровень

14 декабря 2018, 09:49

Задача очень даже хороша на логику сравнения - тут даже меньше использование динамического массива. Решил сравнительно быстро, самая большая сложность - начальные данные и не запутаться в ветке if сравнения - это пока в детском садике программирования самое сложное =) ООП - это уже средняя школа

Rif17 уровень

7 декабря 2018, 10:41

Да уж. Валидатор не пропускает задачу на самую длинную последовательность из-за ошибки "Убедитесь что задача решается для чисел больше 127". И ведь специально настаивали на условии ArrayList с типом элементов Integer, зная что будет такая ошибка. Нас хотят ткнуть носом в баг java - помните int != Integer, и тогда начинаются извраты с преобразованием Integer в int, или вообще использование equals. Я выкрутился так if ((int)nums.get(i - 1) == (int)nums.get(i))

ien10 уровень, Минск

6 января, 00:40

хз делал через for each с внутренним простым ветвлением

Tema Leontev14 уровень

7 февраля, 23:17

int a = list.get(i); int b = list.get (i+1); Дальше сравнивать смело числа от 128 и больше.