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

Открыта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ice8 уровень, Одесса

2 часа назад

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

Андрей13 уровень, Новосибирск

7 июня, 16:35

Обязательно вспомните перед решением задачи "Cамая длинная последовательность", чем различаются типы int и Integer, этим сэкономите кучу времени))

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

18 июня, 23:48

ну как кучу... примерно 3 минуты

Ice8 уровень, Одесса

2 часа назад

так валидатор же сразу прямо намекает, а там действительно минута гугления

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

4 июня, 10:11

Валидатор не принимает задачу, которая работает... Пишет: "В методе main объяви переменную типа List с типом элементов Integer и сразу проинициализируй ee." А это тогда что у меня в коде?: ArrayList<Integer> list = new ArrayList<Integer>();

Stanislav Kulagin13 уровень, Днепр

4 июня, 10:29

Это у вас переменная типа ArrayList, а нужна переменная типа List. Попробуйте вот так: List<Integer> list = new ArrayList<>();

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

4 июня, 15:24

Благодарю! Точно!)

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

25 мая, 09:00

ArrayList LinkedList Взятие элемента get Быстро Медленно Присваивание элемента set Быстро Медленно Добавление элемента add Быстро Быстро Вставка элемента add(i, value) Медленно Быстро Удаление элемента remove Медленно Быстро

Александр20 уровень, Москва

18 мая, 12:53

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

Ivan18 уровень, Череповец

30 мая, 15:52

Были такие же мысли, но самая бредовая победила - потратил время, но не скажу что совсем в пустую)

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

13 мая, 17:56

Решил только накопипастив с различных форумов и подправляя код...сижу теперь перевожу что я вообще сделал)

Lev Afanasov17 уровень, Новосибирск

15 мая, 23:36

про какую задачу речь?

Alukard19 уровень, London

15 мая, 23:43

Видимо про все :D

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

30 апреля, 12:47

"Самая длинная последовательность" заставила попотеть, а по факту нужно было вместо привычного list.get(i) == list.get(i - 1) написать: list.get(i).equals(list.get(i - 1)) поскольку по условию у нас не примитивные int, а Integer

+21

Alukard19 уровень, London

1 мая, 18:08

Тоже на этом срезался.

Alexandr Mihailovich20 уровень, Kursk

3 мая, 21:55

.compareTo() тоже как вариант

Сергей Качан26 уровень, Киев

15 мая, 19:10

(int)list.get(i) == (int)list.get(i - 1) 😀

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

26 мая, 17:08

Спасибо огромное! Благодаря Вам справилась относительно быстро 🙂

dolcom11 уровень, Самара

20 июня, 08:06

А Вы молодец, надо сказать. Задача-то, и правда, не из лёгких

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

20 июня, 09:20

Спасибо на добром слове! Стараемся. Читаю вот дополнительно всего и Ваши комментарии с умными подсказками, конечно, помогают!

Ice8 уровень, Одесса

2 часа назад

Можно и так: iter0.next().compareTo(iter1.next()) == 0

Виталий8 уровень, Ставрополь

29 апреля, 20:25

Как я долго мучался. Наверное задача немного опережается время. Однако полезно так размять мозги

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

23 апреля, 19:43

В последней задаче, у кого проблемы с 4м условием. Валидатор принимает только использование ArrayList

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

29 апреля, 02:45

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

Алексей9 уровень, Ural

27 мая, 11:22

Спасибо, очень выручили

Viktor F3ss17 уровень, Vologda

15 июня, 04:09

с 31 попытки.... последнее условие проходило, а 4 нет, как так. Спасибо)

Егор Гудков10 уровень, Санкт-Петербург

18 апреля, 20:34

В последней задаче ругается на Программа должна выводить на экран длину самой длинной последовательности повторяющихся чисел в списке., хотя при этом всё корректно считается в разных вариантах. Никак не пойму, что ей надо ( Алгоритм: 1. считываю 10 чисел 2. max и tmpmax = 1 3. в цикле начиная с 1 проверяю через .equals текущее значение списка с предыдущим 4. если равны, tmpmax++ если не раны, сравниваю max и tmpmax, tmpmax присваиваю 1 5. после цикла еще раз сравниваю max и tmpmax и вывожу.

Evgeny Mishurov8 уровень, Волгоград

24 мая, 06:35

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

Alexey Naumenko13 уровень, Самара

30 мая, 22:59

к 4тому добавил бы (если в коде нет ) --> если равны, tmpmax++ (и вот тут надо темповский сравнивать то же с мах - и если мах меньше - обновлять значение и у мах)