JavaRush/Java Форум/Сравнение скорости работы ArrayList и LinkedList

30 уровень

13.05.2021
5271просмотров
25комментариев

Сравнение скорости работы ArrayList и LinkedList

Решил у себя потестить, и результаты оказались неожиданными: ArrayList проигрывает LinkedList-у только при добавлении / удалении элементов из начала списка. (а так же потенциально проигрывает при добавлении / удалении с конца списка, если список на миллиарды элементов) Тестил так: создал ArrayList и LinkedList каждый на миллион элементов и выполнял каждую операцию 100000 раз. Вот результаты: Добавление в начало: ArrayList: 25990 мс LinkedList: 7 мс Удаление из начала: ArrayList: 22425 мс LinkedList: 5 мс Добавление в середину: ArrayList: 10676 мс LinkedList: 306245 мс Удаление из середины: ArrayList: 9264 мс LinkedList: 289440 мс Добавление в конец: ArrayList: 5 мс LinkedList: 5 мс Удаление c конца: ArrayList: 30 мс LinkedList: 14 мс Взятие по индексу из середины: ArrayList: 6 мс LinkedList: 305928 мс Присваивание по индексу из середины: ArrayList: 7 мс LinkedList: 305045 мс Взятие по индексу в начале: ArrayList: 5 мс LinkedList: 11 мс Взятие по индексу в конце: ArrayList: 5 мс LinkedList: 3 мс Вывод: используйте LinkedList только если нам нужно много раз делать операции с элементами в начале или в конце списка. В остальных случаях - ArrayList P.S. Когда писал комментарий, то забыл, что у LinkedList можно получить итератор и начинать вставлять элементы с нужного места. В таком случае действительно - все операции по вставке и удалении из середины выполняются буквально за пару миллисекунд. Это пригодится, если нам надо все время вставлять элементы в одно и то же место

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

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

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

Дмитрий

Уровень 19

21 июля 2021, 05:59

Создатель LinkedList писал толи в ФБ у себя, толи в Твиттере, что его LinkedList довольно отстойный) Интересовался использует ли его кто-нибудь, потому что он сам за 20 лет ни разу его не использовал. И скорость ArrayList связана с тем, что его оптимизировали на очень низком уровне, плюс сама ОС ускоряет его, используя каким-то там образом толи кэш процессора, толи спец. регистры. Из-за чего копирование происходит супер быстро

Justinian Judge в Mega City One

Master

21 июля 2021, 07:32

Создатель LinkedList писал толи в ФБ у себя, толи в Твиттере, что его LinkedList довольно отстойный)

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

Сергеев Виктор

Уровень 40

Master

21 июля 2021, 10:30

Писал, не отстой конечно, это уже испорченный телефон )

Joshua Bloch @joshbloch В ответ @jerrykuch @jerrykuch@shipilev@AmbientLion Does anyone actually use LinkedList? I wrote it, and I never use it. https://twitter.com/joshbloch/status/583813919019573248

Justinian Judge в Mega City One

Master

21 июля 2021, 10:50

Писал, не отстой конечно, это уже испорченный телефон )

Да, испорченный телефон, но я исходил из того, либо Джошуа Блох писал что отстой, либо не писал :) 1 или 0 :) То что писал, но писал другое, это значит что он писал другое, а первоначальное не писал :)

Сергеев Виктор

Уровень 40

Master

21 июля 2021, 11:02

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

Justinian Judge в Mega City One

Master

21 июля 2021, 12:51

ага ) джависты уровня Блоха, Мартина и ко живут в своем высокоуровневом мире, иногда спускаясь к нам и на скрижалях предоставляя, то джаву, то солид, потом обратно поднимаясь и дальше живут в своей тусовке небожителей :) А мы внизу, это все применяем ) Разные миры, мир теории, мир практики, одно не может без другого и наоборот, инь и янь

Филипп

Уровень 27

13 мая 2021, 18:42

Тагир Фаридович Валеев из jetbrains в лекции про коллекции упоминал, что ArrayList много раз оптимизировали, а LinkedList нет. Потому он совершенно устарел и почти любую задачу можно решить через ArrayList быстрее и эффективнее. Сохранил себе памятку, что не стоит ииспользовать оттуда:

Сама лекция: https://youtu.be/lCgSsaRdEYU

Justinian Judge в Mega City One

Master

13 мая 2021, 21:16

почти любую задачу можно решить через ArrayList быстрее и эффективнее.

вся соль в слове "почти"

Евгений Backend Developer в KHAN Group

Expert

14 мая 2021, 17:29

Хм. А где он вообще может пригодиться? Честно говоря всегда либо листы использовал, либо очереди.

hidden #2322530

Уровень 41

14 мая 2021, 18:05

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

Евгений Backend Developer в KHAN Group

Expert

14 мая 2021, 18:11

Это да)

Justinian Judge в Mega City One

Master

15 мая 2021, 01:59

К примеру, если нам нужен List и много добавлять/удалять в начало/конец, при этом не нужно итерироваться или искать по значению. Эволюция использования и понимания инструментов выглядит примерно так: 1 стадия. Начинающий разработчик, я узнал о существовании регексов/спринга/хибернейта/мультипоточности, проникся какая это классная штука, и начал использовать везде. Надо посчитать 2+2? Можно же быстрее это сделать с мультипоточностью. Что-то связанно с вэб? Спринг, да побольше его фреймворков без вариантов. Все же юзают спринг и я буду. В строке "id=3" нужно поменять 3 на 4? Трехэтажную регулярку в студию! Работаем с БД? Ну куда же без хибернейта, он ведь сокращает код! На самом деле, ничего плохого в этой стадии нет, это как у детей, увидел, что Петя всунул голову в батарею, о, а ведь я тоже так могу! Так нарабатывается важный практический опыт, это метод научного эксперимента :) 2 стадия. Здесь мы уже суммируем некий опыт с первой + читаем советы и смотрим что используется. Мы формируем границы разумного использования. 3 стадия. По мере углубления теории и практического опыта мы уже не на стадии бездумного повторения, а на стадии осознанного применения и приходим к тому, что нет хороших или плохих инструментов. Есть инструменты, которые в конкретной ситуации предпочтительнее других. С линкедлистом проблема в том, что не так просто объяснить на пальцах когда его использовать, поскольку это редкие и нестандартные кейсы, которые сложно обобщить. + можно почитать еще на тему: - when-to-use-linkedlist-over-arraylist-in-java - java-arraylist-vs-linkedlist/ - linked-lists-performance-evaluation/

Oleksandr Bahno Мечтаю работать програмис в хоть где-то

15 октября 2020, 19:20

Тот же вопрос как и Людмилы. Покажите пример кода со вставкой по итератору

fog

Уровень 18

13 мая 2021, 16:16

А что там показывать?! И ArrayList и LinkedList являются потомками AbstractList, соответственно, предоставляют метод listIterator(), который возвращает объект, реализующий интерфейс ListIterator, а там уже не сложно разобраться...

Людмила

Уровень 20

3 февраля 2020, 17:07

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

fog

Уровень 18

13 мая 2021, 16:16

Людмила

Уровень 20

14 мая 2021, 15:19

Я просто люблю ковыряться в коде)))

Алексей Боярчук

Уровень 30

27 сентября 2019, 16:24

Да, мой косяк. Совсем забыл про итератор. Спасибо за поправку

Михаил

Уровень 12

24 сентября 2019, 10:32

вот результаты теста вставки в середину LinkedList из 1e+6 элементов, 10000 элементов. вариант со вставкой по итератору: 14 мс вариант со вставкой llist.add(llist.size()/2, Object): 32935 мс

Михаил

Уровень 12

24 сентября 2019, 05:36

Безусловно нужно произвести поиск середины. Вопрос в том, сколько раз. Допустим, имеется таблица/linkedlist из 1000 значений куда нужно вставить 1000 строк в середину. Одно дело, если мы находим строку номер 500 берем ее итератор и вставляем после нее 1000 новых строк или новый список из строк, что будет еще несколько быстрее, так как старый список может просто подцепить указатели на начало и конец нового и операций будет произведено меньше. А другое, если мы каждый раз идем от начала списка до 500 строки, вставляем одну строку и забываем о том что мы уже нашли середину. Можно легко прикинуть порядок операций: Допустим, вставка одной строки занимает 3х операций. *Создать объект *Поменять указатель предыдущего элемента. *Поменять указатель следующего элемента . *Поиск середины занимает Size/2 операций. Тогда, для вставки в середину списка из 1000 элементов 1000 новых будет занимать: 1000*3+1000*(500+501) = 1004000 операций, что чуть более чем дофига, причем время работы будет сильно возрастать относительно размеров массива. Но, если вы находите итератор на середину массива, а потом вставляете по нему 1000 раз, то это будет занимать 500+1000*3= 3500 операций. Если же вы вставляете уже готовый массив, то это будет где-то 500+2 = 502 операции.

Eiffil

Уровень 41

23 сентября 2019, 19:06

у меня к сожалению нет опыта программирования на java, но 12 лет на 1С. Там тоже иногда нужно реализовывать алгоритмы вставки строк в середину таблицы значений, а не в конец. И в большинстве случаев перед этим сначала нужно найти строку (позицию), куда эти данные вставлять.

Михаил

Уровень 12

23 сентября 2019, 04:54

На самом деле, вызывает вопрос реализация теста. По идее вставка в середину LinkedList по времени не должна отличаться от любой другой вставки и единственное объяснение данному феномену которое я вижу в том, что Алексей каждый раз искал середину перед вставкой, а время учитывал общее (поиск+вставка) и именно этим обусловлены цифры. Это не совсем корректно и вводит в заблуждение, так как выигрыш в производительности LinkedList будет тогда, когда итератор на середину не определяется каждую вставку.

Larton

Уровень 15

9 сентября 2019, 14:54

Тоже добавлю. Копипаста с хабра, но очень полезная. Почему LinkedList рекомендуется не использовать? 1) он требует в шесть раз больше памяти чем ArrayList (примерно в 4 раза чем ArrayDeque), даже с учетом выделения ArrayList памяти с запасом, все равно по памяти он проигрывает, 2) случаи, когда он будет выигрывать у ArrayList/ArrayDeque встречаются не так часто, так как даже с учетом вставки в середину, итерирование сильно бьет по производительности. То есть он хорош только если надо часто вставлять или удалять данные в серединe списка и при этом практически «не двигаться», что довольно редкий случай. На оф.сайте рекомендую всегда перед выбором Linkedlist сравнить производительность алгоритма по сравнению с ArrayList/ArrayDeque, так как чаще всего выигрыша не будет, даже при вставках внутри листа, 3) если есть возможность использовать Apache Common Collections, то TreeList на основе дерева намного лучшая альтернатива для LinkedList, так как и вставка внутрь списка происходит быстро и получение данных по индексу тоже быстрое. В целом, LinkedList можно использовать в довольно редких случаях, если Apache Common Collections ну никак в проекте использовать нельзя (что я встречал довольно редко).

+37