Pourquoi ArrayDeque est mieux que LinkedList

je crois que le principal goulot d'étranglement de performance dans LinkedList est le fait que chaque fois que vous poussez à n'importe quelle extrémité de la deque, derrière la scène, l'implémentation alloue un nouveau noeud de liste lié, qui implique essentiellement JVM/OS, et c'est coûteux. En outre, chaque fois que vous sautez de n'importe quelle extrémité, les noeuds internes de LinkedList deviennent éligibles pour la collecte des ordures et c'est plus de travail derrière la scène. En outre, puisque les noeuds de liste liés sont alloués ici et là, l'utilisation de CPU le cache ne sera pas très utile.

Si cela peut intéresser, j'ai une preuve que l'ajout d'un élément ArrayList ou ArrayDeque s'exécute en temps constant amorti; reportez-vous à ce .

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'attribuez pas un noeud pour chaque élément à insérer; à la place, tous les éléments sont stockés dans un tableau géant, qui est redimensionné s'il est plein.

tous les gens qui critiquent un LinkedList , pensez à tous les autres gars qui ont utilisé List en Java utilise probablement ArrayList et un LinkedList la plupart 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 's ou ArrayDeque 's side. Si vous voulez savoir, jetez un oeil au-dessous de référence fait par Brian .

le montage d'essai prend en compte:

• chaque objet d'essai est une chaîne de 500 caractères. Chaque chaîne est un objet différent dans la mémoire.
• la taille du réseau d'essai variera pendant les essais.
• pour chaque combinaison taille/file d'attente-implémentation, 100 tests sont exécutés et le temps moyen par test est calculé.
• chacun des tests consiste à remplir chaque file d'attente avec tous les objets, puis de les retirer.
• Mesurer le temps en millisecondes.

Résultat De L'Essai:

• en dessous de 10 000 éléments, les deux tests LinkedList et ArrayDeque moyenne à un niveau inférieur à 1 ms.
• comme les ensembles de données deviennent plus grands, les différences entre le Arraydequeque et LinkedList le temps de test moyen est plus long.
• à la taille d'essai de 9 900 000 éléments, l'approche de la liste maillée a pris ~165% de plus que l'approche ArrayDeque.

graphe:

à emporter:

• si votre besoin est de stocker 100 ou 200 éléments, il ne pas faire 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 ArrayList ou ArrayDeque avec une bonne idée de la capacité maximale que la liste peut être nécessaire à cause d'une contrainte de mémoire stricte.
• beaucoup de code existe, écrit en utilisant un LinkedList donc tread soigneusement lors de la décision d'utiliser un ArrayDeque surtout parce qu'il ne met pas en œuvre la List interface (je pense que la raison est assez grande). Il se peut que votre codebase parle beaucoup à L'interface List, très probablement et que vous décidiez de sauter avec un ArrayDeque . L'utiliser pour des implémentations internes pourrait être une bonne idée...

accéder à un élément dans Arraydequeque est toujours plus rapide comparé à LinkedList avec O(1) pour accéder aux éléments. Dans la liste liée, il faudra O (N) pour trouver le dernier élément.

ArrayDeque est efficace de mémoire puisque vous n'avez pas à garder la trace du prochain noeud contrairement à la liste liée.

même selon la documentation java, il a été cité que

ArrayDeque est Redimensionnable-tableau de mise en œuvre de la Deque interface. Les deques de tableau n'ont pas de restrictions de capacité; ils se développent comme nécessaire pour soutenir l'utilisation. Ils ne sont pas thread-safe; en l'absence de synchronisation externe, ils ne prennent pas en charge l'accès simultané par plusieurs threads. Les éléments Nuls sont interdits. Cette classe est susceptible d'être plus rapide que Stack lorsqu'elle est utilisée comme une pile, et plus rapide que LinkedList lorsqu'elle est utilisée comme file d'attente.

Benchmarking de ces deux prouve que ArrayDeque est plus rapide.

bien que ArrayDeque<E> et LinkedList<E> ont tous les deux mis en œuvre Deque<E> Interface, mais L'ArrayDeque utilise essentiellement objet array E[] pour garder les éléments à l'intérieur de son objet, de sorte qu'il utilise généralement l'index pour localiser la tête et la queue elements.

en un mot, il fonctionne juste comme Deque( avec toute la méthode de Deque), cependant utilise les données du tableau structure. En ce qui concerne celui qui est meilleur, dépend de comment et où vous les utilisez.

le Temps de la complexité pour ArrayDeque pour accéder à un élément de O(1) et que, pour LinkList est est O(N) pour l'accès au dernier élément. ArrayDeque n'est pas sûr de thread donc la synchronisation manuelle est nécessaire afin que vous puissiez y accéder à travers plusieurs threads et donc ils sont plus rapides.