[Из песочницы] Сравнение скорости работы ArrayList и LinkedList на практике

Приветствую Вас!

ArrayList и LinkedList — знают все. В каких ситуациях работает быстро, а в какой ситуации работает медленной тот или другой список — знают тоже все, кто в теории, а кто на практике. Данный пост подходит для тех, кто только начинает изучать Java, или кто слышал, о том «что быстрее», но не видел на практике.



Рекомендую предварительно прочитать расширенные посты про работу:

ArrayList — http://ift.tt/1BwDwJL

LinkedList — http://ift.tt/1rRtVqb

Почему решил измерять? Потому, что после изучения информации остались пробелы, где и что всё-таки быстрее. Особенно сподвиг прочтенный комментарий к статье про LinkedList:

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

Начнем. Как замерял?

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

Пример кода, с помощью которого делал один из типов замеров:

Date startLinked = new Date(); for(int i = 0; i < k; i++) { //операция .add .insert. remove. get .set с начала середины, и конца списка //k - кол-во операций } Date finishLinked = new Date(); long linkedTime = finishLinked.getTime() - startLinked.getTime();

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

Выходные данные

==============Add====================

---Add elements ( 6kk )

LinkedList: 2264 ms

ArrayList: 493 ms

ArrayList is faster

==============Insert=================

---Insert elements to begin( 100k )

LinkedList: 132 ms

ArrayList: 2742 ms

LinkedList is faster

---Insert elements to middle( 60k )

LinkedList: 4110 ms

ArrayList: 494 ms

ArrayList is faster

---Insert elements to end( 1kk )

LinkedList: 35 ms

ArrayList: 119 ms

LinkedList is faster

==============Remove=================

---Remove elements from begin ( 100k )

LinkedList: 2 ms

ArrayList: 3220 ms

ArrayList is faster

---Remove elements from middle ( 100k )

LinkedList: 7519 ms

ArrayList: 1544 ms

ArrayList is faster

---Remove elements from end ( 1kk )

LinkedList: 37 ms

ArrayList: 8 ms

ArrayList is ~faster

==============Get====================

---Get elements from begin ( 4kk )

LinkedList: 25 ms

ArrayList: 7 ms

LinkedList is faster

---Get elements from middle ( 40k )

LinkedList: 2320 ms

ArrayList: 0 ms

ArrayList is faster

---Get elements from end ( 3kk )

LinkedList: 23 ms

ArrayList: 5 ms

ArrayList is faster

==============Set====================

---Set elements at begin ( 1kk )

LinkedList: 342 ms

ArrayList: 12 ms

ArrayList is faster

---Set elements at middle ( 50k )

LinkedList: 3734 ms

ArrayList: 1 ms

ArrayList is faster

---Set elements at end ( 3kk )

LinkedList: 40 ms

ArrayList: 267 ms

ArrayList is faster

==============Finish=================

Выводы

Подытоживая полученные данные, имеем следующее: LinkedList в подавляющем большинстве случаев проигрывает ArrayList, но в оставшемся меньшинстве он вне конкуренции.

Когда использовать LinkedList:

1. Необходимо много данных добавлять в начало и конец списка

2. Удалять с начала (index = 0) списка, т.е. элементы, которые были добавлены первыми.

Когда использовать ArrayList

1. .get

2. .set

3. .add

4. remove ( кроме начала списка )

Интересные факт(!)

.add(linkedList.size()-1, value) — выполняется быстрее в LinkedList

.add(value) — выполняется быстрее в ArrayList

Хотя суть операции та же — добавление в конец списка

Возможно это связанно с отсутствием проверка на длину ArrayList при add(index, value), но до конца не уверен.

Пишите в комментарии замечания/предложения — буду корректировать, пока не найдём истину.

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.