Dlaczego ArrayDeque jest lepszy niż LinkedList

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.

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.

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 .

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.

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:

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 ...

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 .

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.

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;
    }
}

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.