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

Открыта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Василий Бабин9 уровень, Москва

среда, 14:26

Cамая длинная последовательность Код работает, но не проходит проверку!

list.get(i) == list.get(i+1)

Пишет ошибку: Убедитесь, что программа работает правильно, если последовательность состоит из чисел, которые больше 127. Хотя программа работает и с больше 127 и количества больше 127 (я проверил), а проверку не проходит. Да вообще что это значит?! Я почитал ниже, что надо использовать int или equals, а это не проходит:

list.get(i) == list.get(i+1)

Но почему прямое сравнение не проходит, думаю из-за оболочки Integer, так как это не простое int, а ссылка? И что это вообще за ошибка такая кто знает разъясните, пожалуйста.

Василий Бабин9 уровень, Москва

среда, 14:52

Ответ нашёл в комментариях к задаче. Спасибо Vladislav Vasilyev! "При старте JVM, создается 128 экземпляров Integer для чисел от 0 до 127 включительно. При раcпаковке, если значение в диапазоне от 0 до 127, переменной присваивается сгенерированная при старте JVM ссылка на экземпляр Integer. Если же присваивается значение более 127, то генерируется новый класс и его ссылка присваивается переменной. Операция сравнения сравнивает только ссылки. Получается если число меньше 127, то ссылки ведут на один и тот же экземпляр Integer. Если больше 127, то ссылки ведут на разные экземпляры независимо от их значения. Поэтому сравнивать по значению надо всегда через equals(). или привести к (int)"

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

вторник, 11:53

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

Павел Андрусов12 уровень, Липецк

вторник, 07:24

в последней задаче криво поставлено условие насчет типа списка (точнее его вовсе нет). при использовании LinkedList ругается на 4 пункт - "Программа должна добавлять в коллекцию 10 чисел, согласно условию.", но не совсем ясно как это сваязано

ram097318 уровень, Набережные Челны

1 января, 18:04

Заполнить лист тестовыми данными: List<Integer> list = new ArrayList<Integer>(Arrays.asList(1,1,1,4,4,4,4,4,4,4));

Евгений12 уровень, Москва

18 января, 16:06

это помогло проверить условие, когда самая длинная последовательность длится до конца List. и проверить после - текущий счетчик не больше ли максимума

Andrew Shemetov8 уровень, Ростов-на-Дону

14 декабря 2019, 21:21

Подскажите, пожалуйста, у меня в последней задаче Самая длинная последовательность есть ошибка: В методе main объяви переменную типа List с типом элементов Integer и сразу проинициализируй ee. В коде всё просто:

ArrayList<Integer> list = new ArrayList<Integer>();

Что у меня не так?

Andrew Shemetov8 уровень, Ростов-на-Дону

14 декабря 2019, 21:27

А что, так можно было? ))

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

Тима35 уровень, Алматы

9 января, 05:42

Насколько я знаю, это и есть полиморфизм, вы работаете с несколькими типами так, будто это один тип, то есть указав для поля list тип List, вы можете присвоить ссылку на объект любого класса реализующего интерфейс List

Василий VAsili48 уровень

10 декабря 2019, 14:01

Я час выводил цифру с наибольшей последовательностью :facepalm... Оказалось все проще - нужно только последовательность 🙃 if (List.get(i - 1).equals(List.get(i))) {nowrep++; ̶n̶u̶m̶ ̶=̶ ̶L̶i̶s̶t̶.̶g̶e̶t̶(̶i̶)̶;̶ } else {nowrep = 1;} ̶i̶f̶ ̶(̶n̶o̶w̶r̶e̶p̶ ̶>̶ ̶r̶e̶p̶m̶a̶x̶)̶ ̶{̶r̶e̶p̶m̶a̶x̶ ̶=̶ ̶n̶o̶w̶r̶e̶p̶;̶ ̶n̶u̶m̶m̶a̶x̶=̶n̶u̶m̶;̶ ̶ ̶}̶

Bogdan _9 уровень, Днепр

5 января, 22:10

Я часов 7 это делал 😰

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

18 ноября 2019, 20:40

if (list.get(i) == list.get(i+1)) так сравнивать неправильно, потому что в аррайс оно хранится по-другому, надо приводить к int, либо использовать equals

+12

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

29 ноября 2019, 11:24

list.get(i).equals(list.get(i-1))

Anton9 уровень

20 декабря 2019, 11:08

И на самом первом, нулевом элементе что получится? Правильно, индекс равен -1... И как?

Антон8 уровень, Казань

29 декабря 2019, 09:46

возможно это сравнение использовалось во втором цикле, в котором проходили со второго элемента (int i = 1). А в первом цикле заполняли лист числами.

brainiac15 уровень, Киев

30 декабря 2019, 10:29

там скорее всего было как-то так:

list.add(Integer.parseInt(reader.readLine()));
            if(i == 0){
                count++;
            }else{
                int x = list.get(i);
                int y = list.get(i-1);
                if(y == x){
                    count++;
                }else{

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

1 января, 12:54

Верно. Для тех, кому интересно, почему так происходит: https://habr.com/ru/post/104231/

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

18 января, 21:07

Уффф. Долго мучался с задачей, всё не хотел смотреть подсказки. В итоге неправильно сравнивал элементы. Спасибо. Ваш комментарий мне помог. И где half life 3??

Михаил22 уровень, Санкт-Петербург

9 ноября 2019, 13:37

В предпоследней задаче (Квартет «Методы») долго не мог сообразить, что нужно просто вернуть сами созданные списки правильного типа

return new ....List();

из условия это не слишком понятно.

Dmitriy22 уровень

3 ноября 2019, 20:40

В последней задаче будьте внимательны при сравнении. list.get() возвращает объект, а не значение.

Artem Diachenko17 уровень, Днепр

26 октября 2019, 15:22

Какие лямбды, вы о чём? Это восьмой уровень. Последняя задача решается обычным for с одним if-else внутри. Два счётчика, текущий и максимальный. Были же подобные задачи в лекциях про массивы.

javaUndefined9 уровень, Стрежевой

4 ноября 2019, 08:57

А я использовал три переменные (счетчик, максимально значение и одна отвечает за previousValue), previousValue мне нужна чтобы сбросить счетчик, но можно и без неё если заглядывать на минус один индекс.