Dlaczego ArrayDeque jest lepszy niż LinkedList

Uważam, że głównym wąskim gardłem wydajności w LinkedList jest fakt, że za każdym razem, gdy naciskasz na jakikolwiek koniec deque, za sceną implementacja przydziela nowy węzeł listy połączonej, który zasadniczo obejmuje JVM / OS, a to jest drogie. Ponadto, za każdym razem, gdy wyskakujesz z dowolnego końca, wewnętrzne węzły LinkedList kwalifikują się do zbierania śmieci, a to więcej pracy za sceną. Ponadto, ponieważ połączone węzły listy są przydzielane tu i ówdzie, użycie pamięci podręcznej CPU nie zapewni wiele korzyści.

Jeśli może to być interesujące, mam dowód, że dodanie elementu do ArrayList lub ArrayDeque przebiega w stałym czasie amortyzowanym; patrz to .

ArrayDeque JEST NOWY w Javie 6, dlatego wiele kodu (zwłaszcza projektów, które starają się być zgodne z wcześniejszymi wersjami Javy) nie używa go.

Jest to" lepsze " w niektórych przypadkach, ponieważ nie przydzielasz węzła dla każdego elementu do wstawienia; zamiast tego wszystkie elementy są przechowywane w gigantycznej tablicy, która jest zmieniana, jeśli jest pełna.

Wszyscy ludzie krytykujący LinkedList, pomyślcie o każdym innym facecie, który używał List w Javie, prawdopodobnie używa ArrayList i LinkedList przez większość czasu, ponieważ byli przed Javą 6 i dlatego, że są one nauczane jako początek w większości książek.

Ale to nie znaczy, że ślepo wziąłbym stronę LinkedList Czy ArrayDeque. Jeśli chcesz wiedzieć, spójrz na poniższy benchmark wykonany przez Briana.

Konfiguracja testu uwzględnia:

• każdy testowany obiekt jest ciągiem 500 znaków. Każdy ciąg znaków jest innym obiektem w pamięci.
• rozmiar tablicy testowej będzie zmieniany podczas testów.
• dla każdej kombinacji rozmiar tablicy/Kolejka-implementacja, uruchamiane jest 100 testów i obliczany jest średni czas na test.
• każdy test polega na wypełnieniu każdej kolejki wszystkimi obiektami, a następnie ich usunięciu.
• mierz czas w milisekundach.

Test Wynik:

• poniżej 10 000 elementów, zarówno testy LinkedList, jak i ArrayDeque uśrednione na poziomie poniżej 1 ms.
• gdy zbiory danych stają się większe, różnice między ArrayDeque i LinkedList średni czas testu stają się większe.
• przy wielkości testu 9,900,000 elementów, podejście LinkedList trwało ~165% dłużej niż podejście ArrayDeque.

Wykres:

• jeśli twoim wymaganiem jest przechowywanie 100 lub 200 elementów, to nie duża różnica w korzystaniu z jednej z kolejek.
• jednak, jeśli rozwijasz się na urządzeniach mobilnych, możesz użyć ArrayList lub ArrayDeque z dobrym domyśleniem maksymalnej pojemności że lista może być wymagana ze względu na ścisłe ograniczenie pamięci.
• istnieje dużo kodu, napisanego za pomocą LinkedList więc postępuj ostrożnie, decydując się na użycie ArrayDeque, zwłaszcza, że nie implementuje interfejsu List (myślę, że to wystarczająco duży powód). Może być tak, że Twoja baza kodowa intensywnie rozmawia z interfejsem listy, najprawdopodobniej i zdecydujesz się wskoczyć z ArrayDeque. Używanie go do wewnętrznych implementacji może być dobrym pomysłem...

Dostęp do elementu w ArrayDeque jest zawsze szybszy w porównaniu do LinkedList Z O(1) dla dostępu do elementów. W Linked list znalezienie ostatniego elementu zajmie O (N).

ArrayDeque jest wydajny w pamięci, ponieważ nie musisz śledzić następnego węzła w przeciwieństwie do listy połączonej.

Nawet zgodnie z dokumentacją Javy, cytowano, że

ArrayDeque jest skalowalną implementacją array interfejsu Deque. Array deques nie mają ograniczeń pojemności; rosną jako niezbędne do obsługi użytkowania. Nie są one bezpieczne dla wątków; w przypadku braku zewnętrznej synchronizacji nie obsługują współbieżnego dostępu przez wiele wątków. Elementy Null są zabronione. Klasa ta jest prawdopodobnie szybsza niż Stack, gdy jest używana jako stos, i szybsza niż LinkedList, gdy jest używana jako Kolejka.

Benchmarking z tych dwóch dowodzi, że ArrayDeque jest szybszy.

Chociaż ArrayDeque<E> oraz LinkedList<E> czy oba wdrożone Deque<E> interfejsu, ale ArrayDeque używa w zasadzie tablicy obiektowej E[] do przechowywania elementów wewnątrz obiektu, więc zwykle używa indeksu do lokalizowania elementów głowy i ogona.

Jednym słowem, po prostu działa jak Deque( z całą metodą Deque' a), jednak używa struktury danych array. Jeśli chodzi o to, który z nich jest lepszy, zależy od tego, jak i gdzie ich używasz.

Złożoność czasowa ArrayDeque dla dostępu do elementu to O(1), A Dla LinkList to O(N), aby uzyskać dostęp do ostatniego elementu. ArrayDeque nie jest bezpieczny wątek, więc ręczna synchronizacja jest konieczna, aby można było uzyskać do niego dostęp przez wiele wątków, a więc są one szybsze.