Test: ArrayList vs LinkedList - zaskakujące wyniki

Ważnym elementem efektywnego programowania w Javie jest znajomość kolekcji. Trzeba je po prostu znać aby wiedzieć, która z nich najlepiej sprawdzi się w danej sytuacji. Zaczynamy wtedy szukać odpowiedzi w internecie i/lub przeglądać ich wewnętrzną implementację. Chyba najczęściej porównywanymi kolekcjami są: ArrayList i LinkedList.

Kiedy używać ArrayList a kiedy LinkedList?

Teoria co do ich użycia jest prosta i można ją streścić w następujący sposób: Jeżeli priorytetem będzie szybkość dostępu do danych (get, set) to powinniśmy zkorzystać z ArrayList, ponieważ kolekcja ta w gruncie rzeczy opiera się na zwykłej tablicy ("rozszerzanej" w miarę potrzeb), gdzie mamy bezpośredni, szybki dostęp do jej zawartości. Jeżeli natomiast przewidujemy częste zmiany rozmiaru danych (add, remove) to powinniśmy zastanowić się nad użyciem LinkedList, ponieważ te operacje powinny trwać tutaj zdecydowanie krócej niż w ArrayList.

Podsumowując, wyniki testów wydajności tych kolekcji powinny wyglądać mniej więcej tak jak jest to przedstawione tutaj (na dole jest mały wykres porównawczy): http://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/

Własne testy

Postanowiłem jednak samemu przeprowadzić testy tych struktur danych i wyniki nieco mnie zdziwiły.

Zdaję sobie sprawę, że nie zapewniłem tym testom laboratoryjnych warunków, ale postarałem się jak mogłem aby były jak najbardziej rzetelne. Wyłączyłem wszystko co mogło działać w tle i zakłócać wyniki (w miarę możliwości), a testy były powtarzane wielokrotnie w celu uśrednienia czasów. Jednak rezultaty moich pseudo badań w niektórych kwestiach znacznie rozmijają się z przedstawioną wcześniej teorią. Oto one:

Jak widać, dla metod add(Object o) oraz remove(int index) - usuwałem ze środka - LinkedList wcale nie wypada lepiej od ArrayList . Dodatkowo czasy uzyskiwane przez LL podczas dodawania elementów są trochę randomowo-kosmiczne. Ponieważ sposób implementacji tych struktur stoi w sprzeczności z rezultatem testów dla metod add i remove, testy te powtórzyłem następnego dnia. Wyniki były bardzo podobne. W związku z powyższym, postanowiłem zasięgnąć pomocy na forum programistycznym 4programmers (które polecam) i tam poradzono mi abym dodatkowo poddał analizie zużycie pamięci obu struktur podczas testowania metody add. Tak też zrobiłem. Dodatkowo testy wykonałem no innym komputerze - notebooku, oraz delikatnie rozszerzyłem granicę ilości danych do 2,5 mln.

Efekty dodatkowych testów wykazały, że LL zużywa więcej pamięci niż AL i być może praca GC (GarbageCollector) wydłuża czasy tej kolekcji i prowadzi niekiedy do anomalii. Są to jednak tylko przypuszczenia.

Wnioski

Być może, moje testy nie były najlepsze na świecie i prawdopodobnie w lepiej przygotowanym, izolowanym środowisku wypadłyby w większej zgodzie z teorią wynikającą bezpośrednio ze sposobu implementacji porównywanych kolekcji. Z drugiej strony, końcowy użytkownik przecież korzysta z programów w różnych okolicznościach systemu, więc być może praktyka jednak różni się nieco od teorii? Ocenę rzetelność tych testów i decyzję w wyborze między ArrayList i LinkedList pozostawiam Wam. Ja jednak chyba częściej będę teraz skłaniał się ku tej pierwszej :)