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

Открыта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Владимир Шмаков22 уровень, Москва

1 марта, 08:22

При решении задачи на сайте выдает ошибки начиная с заполнения списка: public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); ArrayList<Integer> list = new ArrayList<Integer>(); System.out.println("start"); int in = 0; for(int i = 0; list.size()<10;i++) {System.out.println(i); in = Integer.parseInt(reader.readLine()); list.add(in); System.out.println(in); } На выходе имеем: start 0 89 1 12 2 12 3 98 4 111 5 42 6 98 7 98 8 98 9 71 10 java.lang.NumberFormatException: null at java.lang.Integer.parseInt(Integer.java:542) at java.lang.Integer.parseInt(Integer.java:615) at com.javarush.task.task08.task0812.Solution.main(Solution.java:21) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at java.lang.reflect.Method.invoke(Method.java:498) Вопрос: Это глюк на сайте или я что-то не так делаю?

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

18 марта, 10:16

Попытайтесь назвать по-другому переменную. in - это название статической переменной класса System, которую Вы кстати тут же и используете (во 2й строке)

Nitrop8 уровень

30 января, 15:22

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

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

30 января, 20:21

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

Игорь22 уровень, Минск

23 марта, 11:03

Комментарий для потомков: не пользуйтесь Date, он устарел. Используйте LocalDate - он очень удобен и гибок.

Aleksei Dobrovolskii23 уровень

28 января, 07:39

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

Pavel16 уровень

18 января, 21:32

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

VN10 уровень

10 апреля, 14:03

знай, что ты не один такой :)

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

17 января, 12:46

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

+10

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

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

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

Павел «tERROR» Куртуков15 уровень

2 марта, 15:37

Я, например, инициализировал единицами, потому что минимальная длина последовательности равна 1, так зачем делать лишние итерации? И цикл по этой же логике нет смысла начинать с 0. В общем-то мелочи, на исход не влияют, но осознавать процесс с целью оптимизации помогает.

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

1 апреля, 09:25

Спасибо за отличную идею ))

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

16 января, 14:27

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

Светлана18 уровень, Минск

27 февраля, 14:42

Где вы берете эти данные?) Наверное выдача результата изменилась.

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

7 марта, 13:16

Когда решаешь задачу в Идее, валидатор выдает число решивших.

Шкипер14 уровень, Минск

25 марта, 15:49

Задачу "Cамая длинная последовательность" вобще решили 15.000

Olga11 уровень

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

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

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

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

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

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

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

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

+19

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

30 января, 22:41

Спасибо

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

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

спасибо

v$nr9 уровень

2 марта, 07:53

Благодарю

ildwine24 уровень

16 марта, 18:36

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

AlexDrob9 уровень

27 марта, 08:06

Спасибо!

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

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

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

Juris 8 уровень

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

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