Dlaczego ArrayDeque jest lepszy niż LinkedList

161

Próbuję zrozumieć, dlaczego ArrayDeque w Javie jest lepszy niż LinkedList w Javie, ponieważ oba implementują interfejs Deque.

Prawie nie widzę kogoś używającego ArrayDeque w swoim kodzie. Gdyby ktoś rzucił więcej światła na sposób implementacji ArrayDeque, byłoby to pomocne.

Jeśli to rozumiem, będę pewniej go używać. Nie mogłem jasno zrozumieć implementacji JDK co do sposobu, w jaki zarządza ona odniesieniami głównymi i końcowymi.

Okrutny
źródło
5
Spójrz na odpowiedź na to pytanie, które zrobiłem kilka dni temu: stackoverflow.com/questions/6129805/…
Renato Dinhani
1
W folderze, w którym masz zainstalowany jdk, znajduje się plik src.zip. Jest to archiwum z kodem źródłowym klas java. Zdecydowanie polecam przestudiowanie struktury tych klas i elementów wewnętrznych, aby lepiej zrozumieć, jak działają klasy Java.

Odpowiedzi:

155

Struktury połączone są prawdopodobnie najgorszymi strukturami do iteracji z brakiem pamięci podręcznej dla każdego elementu. Do tego zużywają znacznie więcej pamięci.

Jeśli potrzebujesz dodać / usunąć oba końce, ArrayDeque jest znacznie lepsza niż lista połączona. Dostęp losowy do każdego elementu jest również O (1) dla cyklicznej kolejki.

Jedyną lepszą operacją na połączonej liście jest usunięcie bieżącego elementu podczas iteracji.

bestsss
źródło
57
Kolejna różnica, o której należy pamiętać: LinkedList obsługuje elementy o wartości null, podczas gdy ArrayDeque nie.
Luke Usherwood
15
Kolejną małą wadą (dla aplikacji czasu rzeczywistego) jest to, że w przypadku operacji wypychania / dodawania zajmuje trochę więcej czasu, gdy wewnętrzna tablica ArrayDeque jest pełna, ponieważ musi podwoić swój rozmiar i skopiować wszystkie dane.
Andrei I
4
@AndreiI, to tylko jedna strona historii. Nawet jeśli wykluczysz koszty iteracji aplikacji w czasie rzeczywistym i możliwość wstępnego przydzielenia wymaganej pojemności, GC może wymagać iteracji całej LinkedList. Zasadniczo przenosisz koszty (które są wyższe do rozruchu) do GC.
bestsss
3
@DavidT. b / c wiąże się to z kosztami GC zwalnianego węzła, przypisanie głowy może również wymagać oznaczenia karty (dla GC ponownie, jeśli LinkedList jest już w dzierżawionym genie) ... i to na szczycie dodatkowego pośrednictwa (cache- miss), aby zwrócić element i ponownie połączyć.
bestsss
1
Ponadto LinkedListwdraża, Listgdy ArrayDequenie. Oznacza to, że LinkedLististnieją metody takie jak indexOflub, remove(int)gdy ArrayDequenie ma. Czasami może to być ważne.
ZhekaKozlov
60

Uważam, że głównym wąskim gardłem wydajności LinkedListjest fakt, że za każdym razem, gdy naciskasz na dowolny koniec deque, za sceną implementacja przydziela nowy węzeł połączonej listy, 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 LinkedListkwalifikują się do zbierania śmieci, a to więcej pracy za kulisami. Ponadto, ponieważ węzły listy połączonej są przydzielane tu i tam, użycie pamięci podręcznej procesora nie zapewni większych korzyści.

Jeśli to może być interesujące, mam dowód, że dodanie (dołączenie) elementu do ArrayListlub ArrayDequedziała w zamortyzowanym stałym czasie; odnoszą się do tego .

coderodde
źródło
26

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

W niektórych przypadkach jest to „lepsze”, ponieważ nie przydzielasz węzła dla każdego wstawianego elementu; zamiast tego wszystkie elementy są przechowywane w gigantycznej tablicy, której rozmiar jest zmieniany, jeśli się zapełni.

Chris Jester-Young
źródło
17

Wszyscy ludzie, którzy krytykują a LinkedList, myślą o każdym innym facecie, który używał Listw Javie, prawdopodobnie używa go ArrayListi przez LinkedListwiększość czasu, ponieważ byli przed Java 6 i dlatego, że są to te, których uczy się na początku w większości książek.

Ale to nie znaczy, będę ślepo brać LinkedList„lub S ArrayDeque” s stronie. Jeśli chcesz wiedzieć, spójrz na poniższy benchmark wykonany przez Briana .

Konfiguracja testowa uwzględnia:

  • Każdy obiekt testowy to ciąg 500 znaków. Każdy ciąg jest innym obiektem w pamięci.
  • Rozmiar tablicy testowej będzie się zmieniał podczas testów.
  • Dla każdej kombinacji rozmiaru tablicy / kolejki i implementacji jest wykonywanych 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 usunięciu ich wszystkich.
  • Mierz czas w milisekundach.

Wynik testu:

  • Poniżej 10 000 elementów testy LinkedList i ArrayDeque uśrednione na poziomie poniżej 1 ms.
  • W miarę zwiększania się zbiorów danych różnice między średnim czasem testu ArrayDeque i LinkedList stają się większe.
  • Przy testowym rozmiarze 9 900 000 elementów podejście LinkedList trwało ~ 165% dłużej niż podejście ArrayDeque.

Wykres:

wprowadź opis obrazu tutaj

Na wynos:

  • Jeśli twoim wymaganiem jest przechowywanie 100 lub 200 elementów, nie miałoby to większego znaczenia przy użyciu żadnej z kolejek.
  • Jeśli jednak tworzysz na urządzeniach mobilnych, możesz chcieć użyć ArrayListlub ArrayDequez dobrym szacunkiem maksymalnej pojemności, jaką może być wymagana lista ze względu na ścisłe ograniczenie pamięci.
  • Istnieje wiele kodu, napisanego z LinkedListtaką ostrożnością przy podejmowaniu decyzji o użyciu, ArrayDequezwłaszcza dlatego, że NIE implementuje Listinterfejsu (myślę, że to wystarczająco duży powód). Może się zdarzyć, że twój kod źródłowy intensywnie komunikuje się z interfejsem List, najprawdopodobniej i zdecydujesz się wskoczyć z plikiem ArrayDeque. Używanie go do wewnętrznych wdrożeń może być dobrym pomysłem ...
Manish Kumar Sharma
źródło
W jaki sposób ten test porównawczy przechwyciłby czas GC spowodowany przez śmieci z połączonej listy?
0xbe5077 wysłane
3

ArrayDeque i LinkedList implementują Deque interfejs , ale implementacja jest inna.

Kluczowe różnice:

  1. ArrayDeque klasa jest skalowalny realizacja tablica z deque interfejsu i LinkedList klasa jest realizacja lista

  2. Elementy NULL można dodawać do LinkedList, ale nie w ArrayDeque

  3. ArrayDeque jest wydajniejszy niż LinkedList do dodawania i usuwania operacji na obu końcach, a implementacja LinkedList jest wydajna do usuwania bieżącego elementu podczas iteracji

  4. LinkedList realizacja zużywa więcej pamięci niż ArrayDeque

Więc jeśli nie musisz obsługiwać elementów NULL i szukasz mniejszej ilości pamięci i wydajności dodawania / usuwania elementów na obu końcach, ArrayDeque jest najlepszym

Więcej informacji można znaleźć w dokumentacji .

Ravindra babu
źródło
13
„Na liście połączonych znalezienie ostatniego elementu zajmie O (N)”. nie jest do końca prawdą. LinkedList jest zaimplementowany jako lista podwójnie połączona, więc nie musisz przechodzić przez listę, aby uzyskać ostatni element ( header.previous.element). Twierdzenie „wydajność pamięci” może również zostać zakwestionowane, ponieważ rozmiar tablicy bazowej jest zawsze zmieniany do następnej potęgi 2.
Clément MATHIEU
5
„Potrzeba O (N), aby znaleźć ostatni element” jest NIEPOPRAWNE. Lista połączona zachowuje odniesienie do ostatniego węzła, a LinkedList.descendingIterator () pobiera ten węzeł. Otrzymujemy więc wydajność O (1). Zobacz: coffeeorientedprogramming.wordpress.com/2018/04/23/… (a więc obniżanie głosów).
Leo Ufimtsev
1
Gdy używasz a, Iteratoraby uzyskać dostęp do ostatniego elementu, operacja jest O (N) dla obu klas. Kiedy używasz wspólnego Dequeinterfejsu, dostęp do ostatniego elementu jest O (1) dla obu klas. Niezależnie od przyjętego punktu widzenia, przypisywanie O (1) do ArrayDequei O (N) LinkedListjednocześnie jest błędne.
Holger
Wszystkie sugestie zostały uwzględnione i poprawione
Ravindra babu
1

chociaż ArrayDeque<E>i LinkedList<E>mają zaimplementowany Deque<E>interfejs, ale ArrayDeque używa w zasadzie tablicy Object E[]do przechowywania elementów wewnątrz obiektu, więc generalnie używa indeksu do lokalizowania elementów head i tail.

Jednym słowem, działa podobnie jak Deque (ze wszystkimi metodami Deque), jednak wykorzystuje strukturę danych tablicy. To, który z nich jest lepszy, zależy od tego, jak i gdzie ich używasz.

rekinyz
źródło
-1

Nie zawsze tak jest.

Na przykład w poniższym przypadku linkedlistma lepszą wydajność niż ArrayDequezgodnie z leetcode 103.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> rs=new ArrayList<>();
        if(root==null)
            return rs;
        // 👇 here ,linkedlist works better
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        boolean left2right=true;
        while(!queue.isEmpty())
        {
            int size=queue.size();
            LinkedList<Integer> t=new LinkedList<>();
            while(size-->0)
            {
                TreeNode tree=queue.remove();
                if(left2right)  
                    t.add(tree.val);
                else
                    t.addFirst(tree.val);
                if(tree.left!=null)
                {
                    queue.add(tree.left);
                }
                if(tree.right!=null)
                {
                    queue.add(tree.right);
                }
            }
            rs.add(t);
            left2right=!left2right;
        }
        return rs;
    }
}
Czerwony
źródło
-5

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

Piyush Yawalkar
źródło
3
Jeśli odnosisz się LinkedListw Javie Collection, jest on podwójnie połączony i ma szybki dostęp do głowy i ogona, więc dostęp do ostatniego elementu również wymaga O (1).
Maurice
Dostęp do ostatniego elementu w LinkedList nie jest O (N). Jeśli używasz descendingIterator (), jest to wykonywane w O (1). Zobacz coffeeorientedprogramming.wordpress.com/2018/04/23/… (stąd głos przeciw).
Leo Ufimtsev
1
Obie klasy nie są bezpieczne dla wątków. I nie ma związku między początkiem zdania „ręczna synchronizacja jest konieczna” a jego końcem „oni są szybsi”.
Holger