Pourquoi ArrayDeque est meilleur que LinkedList

161

J'essaie de comprendre pourquoi ArrayDeque de Java est meilleur que LinkedList de Java car ils implémentent tous les deux l'interface Deque.

Je vois à peine quelqu'un utiliser ArrayDeque dans son code. Si quelqu'un met plus de lumière sur la manière dont ArrayDeque est implémenté, ce serait utile.

Si je le comprends, je serai plus confiant de l'utiliser. Je ne pouvais pas comprendre clairement l'implémentation JDK quant à la façon dont elle gère les références tête et queue.

Cruel
la source
5
Regardez la réponse à cette question que j'ai faite il y a quelques jours: stackoverflow.com/questions/6129805/…
Renato Dinhani
1
Dans le dossier où vous avez installé votre jdk, il y a un fichier src.zip. C'est l'archive avec le code source des classes java. Je recommande fortement d'étudier la structure et les éléments internes de ces classes pour mieux comprendre le fonctionnement des classes Java.

Réponses:

155

Les structures liées sont probablement la pire structure à itérer avec un cache manquant sur chaque élément. De plus, ils consomment beaucoup plus de mémoire.

Si vous avez besoin d'ajouter / supprimer les deux extrémités, ArrayDeque est nettement meilleur qu'une liste liée. L'accès aléatoire à chaque élément est également O (1) pour une file d'attente cyclique.

La seule meilleure opération d'une liste chaînée est de supprimer l'élément actuel pendant l'itération.

bestsss
la source
57
Autre différence à garder à l'esprit: LinkedList prend en charge les éléments nuls, contrairement à ArrayDeque.
Luke Usherwood
15
Un autre petit inconvénient (pour les applications en temps réel) est que lors d'une opération push / add, il en faut un peu plus lorsque le tableau interne du ArrayDeque est plein, car il doit doubler sa taille et copier toutes les données.
Andrei I
4
@AndreiI, ce n'est qu'une facette de l'histoire. Même si vous excluez les coûts d'itération pour une application en temps réel et la possibilité de préallouer la capacité nécessaire, le GC peut avoir besoin d'itérer toute la LinkedList. En gros, vous transférez les coûts (qui sont plus élevés pour démarrer) dans le GC.
bestsss
3
@DavidT. b / c cela implique des coûts GC du nœud libéré, l'attribution de la tête peut également nécessiter un marquage de carte (pour le GC encore une fois, si la LinkedList est déjà dans la génération titulaire) ... et c'est en plus de l'indirection supplémentaire (cache- miss) pour renvoyer l'élément et le relier.
bestsss
1
En outre, LinkedListimplémente Listtandis ArrayDequeque non. Cela signifie que vous LinkedListavez des méthodes comme indexOfou remove(int)pendant que ArrayDequenon. Cela peut parfois être important.
ZhekaKozlov
60

Je pense que le principal goulot d'étranglement des performances LinkedListréside dans le fait que chaque fois que vous poussez à n'importe quelle extrémité du deque, dans les coulisses, la mise en œuvre alloue un nouveau nœud de liste chaînée, qui implique essentiellement JVM / OS, et c'est cher. De plus, chaque fois que vous sortez de n'importe quelle extrémité, les nœuds internes LinkedListdeviennent éligibles pour le garbage collection et c'est plus de travail en arrière-plan. De plus, étant donné que les nœuds de la liste liée sont alloués ici et là, l'utilisation du cache du processeur ne fournira pas beaucoup d'avantages.

Si cela peut être intéressant, j'ai une preuve que l'ajout (ajout) d'un élément à ArrayListou ArrayDeques'exécute en temps constant amorti; référez-vous à cela .

coderodde
la source
26

ArrayDeque est nouveau avec Java 6, c'est pourquoi beaucoup de code (en particulier les projets qui essaient d'être compatibles avec les versions précédentes de Java) ne l'utilisent pas.

C'est «mieux» dans certains cas parce que vous n'allouez pas de nœud pour chaque élément à insérer; au lieu de cela, tous les éléments sont stockés dans un tableau géant, qui est redimensionné s'il est plein.

Chris Jester-Young
la source
17

Tous les gens qui critiquent un LinkedList, pensent à tous les autres gars qui ont utilisé Listen Java utilisent probablement ArrayListet la LinkedListplupart du temps parce qu'ils ont été avant Java 6 et parce que ce sont ceux qui sont enseignés comme un début dans la plupart des livres.

Mais, cela ne veut pas dire, je prendrais aveuglément LinkedList« ou de ArrayDeque» côté s. Si vous voulez savoir, jetez un œil au benchmark ci-dessous réalisé par Brian .

La configuration du test prend en compte:

  • Chaque objet de test est une chaîne de 500 caractères. Chaque chaîne est un objet différent en mémoire.
  • La taille du tableau de test variera au cours des tests.
  • Pour chaque combinaison taille de tableau / mise en œuvre de file d'attente, 100 tests sont exécutés et le temps moyen par test est calculé.
  • Chaque test consiste à remplir chaque file d'attente avec tous les objets, puis à les supprimer tous.
  • Mesurez le temps en millisecondes.

Résultat du test:

  • En dessous de 10 000 éléments, les tests LinkedList et ArrayDeque ont obtenu une moyenne à un niveau inférieur à 1 ms.
  • Au fur et à mesure que les ensembles de données s'agrandissent, les différences entre le temps de test moyen d'ArrayDeque et LinkedList s'agrandissent.
  • À la taille de test de 9 900 000 éléments, l'approche LinkedList a pris environ 165% de plus que l'approche ArrayDeque.

Graphique:

entrez la description de l'image ici

À emporter:

  • Si votre besoin est de stocker 100 ou 200 éléments, cela ne ferait pas beaucoup de différence en utilisant l'une ou l'autre des files d'attente.
  • Cependant, si vous développez sur mobile, vous pouvez utiliser un ArrayListou ArrayDequeavec une bonne estimation de la capacité maximale que la liste peut être requise en raison d'une contrainte de mémoire stricte.
  • Il existe beaucoup de code, écrit en utilisant une LinkedListbande de roulement tellement prudente au moment de décider d'utiliser un, en ArrayDequeparticulier parce qu'il n'implémente PAS l' Listinterface (je pense que c'est une raison assez grande). Il se peut que votre base de code communique beaucoup avec l'interface List, très probablement et que vous décidez de vous lancer avec un ArrayDeque. L'utiliser pour des implémentations internes pourrait être une bonne idée ...
Manish Kumar Sharma
la source
Comment ce benchmark capturerait-il le temps GC causé par les déchets de la liste chaînée?
0xbe5077 du
3

ArrayDeque et LinkedList implémentent Deque interface mais l'implémentation est différente.

Principales différences:

  1. La classe ArrayDeque est l'implémentation de tableau redimensionnable de l' interface Deque et la classe LinkedList est l'implémentation de la liste

  2. Les éléments NULL peuvent être ajoutés à LinkedList mais pas dans ArrayDeque

  3. ArrayDeque est plus efficace que LinkedList pour l'opération d'ajout et de suppression aux deux extrémités et l'implémentation de LinkedList est efficace pour supprimer l'élément actuel pendant l'itération

  4. L' implémentation LinkedList consomme plus de mémoire que ArrayDeque

Donc, si vous n'avez pas à prendre en charge les éléments NULL && à la recherche de moins de mémoire && efficacité d'ajout / suppression d'éléments aux deux extrémités, ArrayDeque est le meilleur

Reportez-vous à la documentation pour plus de détails.

Ravindra babu
la source
13
"Dans la liste Linked, il faudra O (N) pour trouver le dernier élément." n'est pas exactement vrai. LinkedList est implémenté comme une liste doublement liée, vous n'avez donc pas à parcourir la liste pour obtenir le dernier élément ( header.previous.element). L'affirmation "efficacité de la mémoire" peut également être contestée puisque le tableau de support est toujours redimensionné à la prochaine puissance de 2.
Clément MATHIEU
5
"Il faudra O (N) pour trouver le dernier élément" est FAUX. La liste liée garde une référence au dernier nœud et LinkedList.descendingIterator () obtient ce nœud. Nous obtenons donc des performances O (1). Voir: coffeeorientedprogramming.wordpress.com/2018/04/23/… (donc vote négatif).
Leo Ufimtsev
1
Lorsque vous utilisez un Iteratorpour accéder au dernier élément, l'opération est O (N) pour les deux classes. Lorsque vous utilisez l' Dequeinterface commune , l'accès au dernier élément est O (1) pour les deux classes. Quel que soit le point de vue que vous adoptez, attribuer O (1) à ArrayDequeet O (N) en LinkedListmême temps est faux.
Holger
Toutes vos suggestions sont prises et corrigées du contenu
Ravindra babu
1

bien que ArrayDeque<E>et LinkedList<E>ont tous deux implémenté Deque<E>Interface, mais ArrayDeque utilise essentiellement un tableau Object E[]pour garder les éléments à l'intérieur de son Object, donc il utilise généralement un index pour localiser les éléments head et tail.

En un mot, cela fonctionne comme Deque (avec toute la méthode Deque), mais utilise la structure de données du tableau. Quant à savoir lequel est le meilleur, cela dépend comment et où vous les utilisez.

Rekinyz
la source
-1

Ce n'est pas toujours le cas.

Par exemple, dans le cas ci-dessous linkedlista de meilleures performances que ArrayDequeselon le 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;
    }
}
rouge
la source
-5

La complexité temporelle pour ArrayDeque pour accéder à un élément est O (1) et celle pour LinkList est O (N) pour accéder au dernier élément. ArrayDeque n'est pas thread-safe, donc une synchronisation manuelle est nécessaire pour que vous puissiez y accéder via plusieurs threads et qu'ils soient plus rapides.

Piyush Yawalkar
la source
3
Si vous faites référence à LinkedListJava Collection, il est doublement lié et a un accès rapide à la tête et à la queue, donc l'accès au dernier élément prend également O (1).
Maurice le
L'accès au dernier élément de LinkedList n'est pas O (N). Si vous utilisez descendingIterator (), il est exécuté dans O (1). Voir coffeeorientedprogramming.wordpress.com/2018/04/23/… (donc vote négatif ).
Leo Ufimtsev
1
Les deux classes ne sont pas thread-safe. Et il n'y a aucun lien entre le début de la phrase «la synchronisation manuelle est nécessaire» et sa fin «ils sont plus rapides».
Holger