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

Открыта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

час назад

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

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

час назад

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

Juris 8 уровень

13 часов назад

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

Rif10 уровень

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

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

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

30 ноября, 22:44

Решил аш с третьей попытки. Не проходил валидацию пункт "Для чисел больше 127.." А всё дело в том, что я сравнивал элементы через ссылки, а надо было через один метод (спойлерить не буду).

Григорий9 уровень

6 декабря, 20:54

ну, я тоже упёрся в эту хрень. А теперь вопрос 127 - это предел типа byte он от -128 до +127 какого хрена так получается если весе переменные объявлены int a список Integer ??? Почему до 127 все работает как Integer а когда перешагиваем предел byte, то Integer резко становится ссылкой и ему срочно нужен equals??? Это кривизна рук разработчиков Java - которую надо постоянно помнить и фиксить при каждом подобном случае? Или это кривизна рук разработчиков этой задачи из команды javarush? P.S. прошёл валидацию с 6 попытки - почувствовал себя дауном... Но кажется меня просто ... (обманули).

Григорий9 уровень

6 декабря, 22:40

да, в этом примере equals легко обходиться или приравнением переменной int к значению Integer

int numI = list.get(i);
int numN = list.get(n);
if (numI == numN) {...}

или путем математического действия со значением Integer - что заставляет Integer стать нормальным int (действие не должно менять значение полученного int) например плюсую ноль

if (list.get(i) + 0 == list.get(n) + 0) {...}

такими нехитрыми способами в данном примере можно обойтись без вызова equals отказ от equals ускорит выполнение программы да и вообще использование метода, если хз как он работает - это зло... и методы от разработчиков java начали у меня вызывать подозрения... (а вычитывать что там насрали разрабы я ещё не готов)

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

7 декабря, 06:16

Так же в начале столкнулся с такой проблемой. Однако быстро понял, что никаких косяков тут нет. Все правильно. Метод get возвращает элемент (Е) , который может быть любым типом. Т.е. ссылочной переменной, а сравнивать ссылочные переменные нужно правильно. В книге "Изучаем Java" подчеркивается, что способ создания ссылочной переменной не такой простой как думается. Скорее всего для ссылок на переменные используются сложные алгоритмы и способ зависит от объекта. Например выделение памяти в куче для Iteger до 128 может совпадать с самим числом, это будет занимать меньше места в памяти. А ссылки на числа от 128 и выше строятся по другому алгоритму.

Григорий9 уровень

7 декабря, 09:14

да, походу костыли ~~(методы)~~ от разработчиков java обладают неприятным эффектом - ломаются постоянно. И это придётся постоянно учитывать в дальнейшей работе. а раздражает то, что вся эта хрень начинает работать как надо, а потом возникает проблема - если бы сразу выдавалась ошибка и конструкция не работала - это было бы правильно. А так получается половинчатая ситуация - явно провокация от полупидаров...

Rif10 уровень

7 декабря, 10:42

Можно было проще if ((int)nums.get(i - 1) == (int)nums.get(i))

Григорий9 уровень

7 декабря, 13:03

точно, забыл про принудительный перевод в нужный тип данных

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

22 ноября, 00:50

Задачу самая длинная последовательность, долго пытался решить, разными извращенными способами) Но в итоге все стер, собрался с мыслями и решил. Решение оказалось не таким уж и сложным, главное поразмыслить. Совет: не придумывайте велосипед (как я), все что надо для решения этой задачи было в предыдущих лекциях, уровнях) Удачи!

Andrii Gorshunov18 уровень

31 октября, 20:35

Cамая длинная последовательность -- СПОЙЛЕР: Задачу "Cамая длинная последовательность" решил таким образом: после того как создал массив, заполнил его через цикл я создал бесконечный цикл while(true) в котором короче еще раз сканировал данные в заполненном ArrayList-e, где сравнивал следующую цифру с предыдущей, если они обе равнялись друг-другу, то увеличивался счетчик. Сам счетчик начинался с 1. Если две эти цифры не равнялись между собой, то счетчик "обнулялся" до начального значения 1. То есть при числах (2, 2, 2, 4, 4, 4, 4, 1, 3, 3) Счетчик имел такие показатели (2, 3, 1, 2, 3, 4, 1, 1, 2, 4). Я данные со счетчика добавлял в новый отдельный ArrayList<Integer> temp. После чего находил максимальное число в этом новом Списке temp. Выводил его в консоль и делал break бесконечно цикла while. Думаю можно было решить задачу иначе. Предлагаю поделиться вашими решениями :)

Вадим13 уровень

3 ноября, 23:32

Берем 3 целочисленные переменные: max = 1 len = 1 ch = arr.get(0) В цикле от 1 до 9 проверяем i-й элемент списка Если arr.get(i) == ch, то увеличиваем len на 1 и идем дальше Если arr.get(i) != ch, то: 1) если len > max, тогда max = len 2) len = 1; 3) ch = arr.get(i); После цикла еще раз проверяем, если len > max, тогда max = len Выводим max

Pavlic Morozov (pashok09i)18 уровень, Екатеринбург

4 ноября, 19:06

можно обойтись 2 целочисленными переменными, если сравнивать через метод equals(); а использую плюсом тернарный оператор, вообще конфетка получается

Константин18 уровень, Екатеринбург

1 октября, 08:45

Писали уже, заострю внимание! Integer - это НЕ int ! Он не является простым типом! И, как следствие, не может быть сравнен через оператор "==", только через метод equals!

Григорий9 уровень

6 декабря, 21:07

До 127 всё работает. А теперь вопрос 127 - это предел типа byte он от -128 до +127 какого хрена так получается если весе переменные объявлены int a список Integer ??? Почему до 127 все работает как Integer а когда перешагиваем предел byte, то Integer резко становится ссылкой и ему срочно нужен equals??? Это особенность реализации класса-оболочки Integer ???

Rif10 уровень

7 декабря, 10:46

Не вводи людей в заблужнение. Есть явное преобразование типов. Можно так if ((int)nums.get(i - 1) == (int)nums.get(i))

Алексей17 уровень, Москва

25 сентября, 02:28

Кто-нибудь, пожалуйста подскажите, что от нас хотят в задании Квартет «Методы»?

Панков Павел18 уровень, Москва

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

Вы должны в каждом методе вернуть один из объектов классов реализующих интерфейс List (ArrayList или LinkedList), но вернуть такой, который будет справляться лучше с поставленной задачей метода. Задача метода обозначена в самом названии метода.

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

7 сентября, 20:09

Предпоследняя задача оказалась для меня трудней, чем последняя, никак не мог понять, чего валидатор хочет. А в последней, как уже писали ниже, для сравнения объектов Integer надо использовать equals, а не ==.