Pourquoi est-ArrayDeque mieux que LinkedList

J'essaie de comprendre pourquoi Java est ArrayDeque est mieux que Java est LinkedList qu'ils mettent en œuvre Deque interface.

J'ai du mal à voir quelqu'un à l'aide de ArrayDeque dans leur code. Si quelqu'un jette plus de lumière dans la façon dont ArrayDeque est mis en œuvre, il serait utile.

Si je comprends bien, je vais être plus confiant en l'utilisant. Je ne pouvais pas comprendre clairement le JDK de mise en œuvre de la façon dont il gère la tête et la queue références.

  • Regardez la réponse à cette question, je l'ai fait il y a de jours: stackoverflow.com/questions/6129805/...
  • Dans le dossier où vous avez votre jdk est installé, il y a un fichier src.zip. C'est l'archive avec le code source des classes java. Je recommande fortement à l'étude de ces classes de la structure et du fonctionnement interne de mieux comprendre comment des classes java de travail.
InformationsquelleAutor Cruel | 2011-05-28
  1. 125

    Structures sont peut-être le pire de la structure de l'itération avec un cache miss sur chaque élément. Sur le dessus de ce qu'ils consomment de manière plus mémoire.

    Si vous avez besoin d'ajouter/supprimer des deux extrémités, ArrayDeque est nettement mieux qu'une liste liée. Accès aléatoire chaque élément est aussi O(1) pour une reprise cyclique de la file d'attente.

    La seule mieux le fonctionnement d'une liste chaînée est la suppression de l'élément courant au cours d'une itération.

    • Une autre différence de garder à l'esprit: LinkedList soutient éléments null, alors que ArrayDeque ne le fait pas.
    • Aussi un autre petit inconvénient (pour les applications en temps réel), c'est que sur un push opération d'ajout/il prend un peu plus de l'intérieur que de l'éventail de la ArrayDeque est plein, comme il a du double de sa taille et de copier toutes les données.
    • ce d'un seul côté de l'histoire. Même si l'on exclut l'itération des coûts pour l'application en temps réel et la capacité de prealloc la capacité nécessaire, le GC peut à itérer l'ensemble de la LinkedList. En gros vous êtes en mouvement les coûts (qui sont plus élevés pour le démarrage), dans la GC.
    • pourquoi l'ajout/retrait sur la tête sera pire pour la LinkedList?
    • b/c il implique GC coûts des libérés nœud, l'attribution de la tête peut également besoin de carte de marquage (pour la GC à nouveau, si la LinkedList est déjà dans le titularisés gen)... et c'est sur le haut de la supplémentaire d'indirection (cache miss) pour revenir à l'élément et à rétablir le lien.
    • Aussi, LinkedList implémente List tout ArrayDeque ne l'est pas. Cela signifie que LinkedList ont des méthodes comme indexOf ou remove(int) tout ArrayDeque n'a pas. Il peut être important parfois.

    InformationsquelleAutor bestsss
  2. 44

    Je crois que le principal goulot d'étranglement des performances dans LinkedList est le fait que chaque fois que vous poussez à la toute fin de la deque, derrière la scène de la mise en œuvre alloue une nouvelle liste liée nœud, ce qui implique essentiellement JVM/OS, et c'est cher. Aussi, chaque fois que vous la pop à partir de la toute fin, les noeuds internes de LinkedList devenir admissibles pour la collecte des ordures et c'est plus de travail derrière la scène.
    Aussi, depuis la liste des nœuds sont répartis ici et là, l'utilisation du cache du PROCESSEUR ne sera pas de fournir beaucoup d'avantages.

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

    InformationsquelleAutor coderodde
  3. 25

    ArrayDeque est une nouveauté de la version 6 de Java, qui est pourquoi beaucoup de code (en particulier les projets qui s'efforcent d'être compatible avec les anciennes versions de Java) ne l'utilisez pas.

    C'est "mieux" dans certains cas, parce que vous n'êtes pas à l'attribution d'un 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ée si elle est pleine.

    InformationsquelleAutor Chris Jester-Young
  4. 10

    Toutes les personnes critiquant un LinkedList, pensez à tous les autres gars qui a été à l'aide de List en Java utilise probablement ArrayList et un LinkedList la plupart du temps parce qu'ils ont été avant de Java 6 et parce que ce sont celles qui sont enseignées comme un début dans la plupart des livres.

    Mais, cela ne signifie pas, je aveuglément prendre LinkedList's ou ArrayDeques'à côté. Si vous voulez savoir, jetez un oeil au-dessous de référence réalisé par Brian.

    La configuration de test à l'estime:

    • Chaque objet de test est un 500 Chaîne de caractères. Chaque Chaîne de caractères est un objet différent dans la mémoire.
    • La taille de l'essai tableau sera varié pendant les tests.
    • Pour chaque taille de tableau/liste d'Attente-mise en œuvre de la combinaison, 100 tests sont exécutés et la moyenne des temps-par-test est calculé.
    • Chaque tests consiste à remplir chaque file d'attente avec tous les objets, puis en supprimant tous.
    • Mesurer le temps en millisecondes.

    Résultat Du Test:

    • En dessous de 10 000 éléments, à la fois LinkedList et ArrayDeque tests en moyenne à un sous 1 ms niveau.
    • Que les ensembles de données sont de plus en plus, les différences entre les ArrayDeque et LinkedList moyenne de temps de test devient plus grand.
    • À l'épreuve de la taille de 9,900,000 éléments, la LinkedList approche a pris ~165% de plus que la ArrayDeque approche.

    Graphique:

    Pourquoi est-ArrayDeque mieux que LinkedList

    À emporter:

    • Si votre exigence est de stocker des 100 ou de 200 éléments, il ne fera pas
      beaucoup de différence à l'aide de l'une des Files d'attente.
    • Toutefois, si vous êtes en développement sur mobile, vous pouvez utiliser un
      ArrayList ou ArrayDeque avec une bonne estimation de leur capacité maximale
      que la liste peut être nécessaire pour être en raison de la stricte contrainte de mémoire.
    • Beaucoup de code existe, écrit à l'aide d'un LinkedList donc faire preuve de prudence lorsque vous décidez d'utiliser un ArrayDeque surtout parce qu'il NE PAS mettre en œuvre la List interface(je pense que c'est une raison assez grand). Il se peut que votre base de code parle à la Liste de l'interface largement, plus probablement et vous décider à sauter à un ArrayDeque. De l'utiliser pour les implémentations internes pourrait être une bonne idée...
    • Quel en serait l'indice de référence de capture de la GC temps causée par la liste liée à ordures?
    InformationsquelleAutor pulp_fiction
  5. 5

    Accéder à un élément dans ArrayDeque est toujours plus rapide par rapport à LinkedList avec O(1) pour accéder à des éléments. Dans la liste chaînée, il faudra du temps O(N) pour trouver le dernier élément.

    ArrayDeque de la mémoire est efficace puisque vous n'avez pas à garder une trace de la prochaine nœud contrairement à la Liste Liée.

    Même que par la documentation java, il a été cité que

    ArrayDeque est Redimensionnable-tableau de mise en œuvre de l'interface Deque. Tableau deques ont pas de restrictions de capacité; elles deviennent nécessaires à l'appui de 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. Null éléments sont interdites. Cette classe est susceptible d'être plus rapide que la Pile lorsqu'il est utilisé comme une pile, et plus vite que LinkedList lorsqu'il est utilisé comme une file d'attente.

    L'analyse comparative de ces deux prouve que ArrayDeque est plus rapide.

    • "Dans la liste chaînée, il faudra du temps O(N) pour trouver le dernier élément." n'est pas exactement vrai. LinkedList est implémenté sous la forme d'une liste doublement chaînée de sorte que vous n'avez pas à parcourir la liste pour obtenir le dernier élément (header.previous.element). La "mémoire de l'efficacité" peut également être remis en question depuis la sauvegarde de la matrice est toujours redimensionnée à la puissance de 2.
    • "Il faudra du temps O(N) pour trouver le dernier élément" est ERRONÉ. Liste liée maintient une référence vers le dernier nœud et LinkedList.descendingIterator() get de ce nœud. Nous obtenons donc O(1) de la performance. Voir: coffeeorientedprogramming.wordpress.com/2018/04/23/... (donc downvoting).
    • Qu'en est normale itérateur au lieu de descendre itérateur? Lorsque vous choisissez un élément dans la liste, vous ne savez pas si c'est en début ou milieu ou à la fin. Donc encore mon post est correct.
    InformationsquelleAutor Ravindra babu
  6. 1

    bien que ArrayDeque<E> et LinkedList<E> ont à la fois mis en œuvre Deque<E> de l'Interface, mais le ArrayDeque utilise fondamentalement tableau d'Objets E[] pour garder les éléments à l'intérieur de son Objet, de sorte qu'il utilise généralement des index pour localiser la tête et la queue éléments.

    En un mot, il fonctionne exactement comme Deque (avec tous les Deque de la méthode), mais utilise la matrice de structure de données. En ce qui concerne qui est mieux, dépend de la manière dont vous les utilisez.

    InformationsquelleAutor rekinyz
  7. -2

    Temps de 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 thread-safe manuellement la synchronisation est nécessaire de sorte que vous pouvez y accéder par plusieurs threads et donc ils sont plus rapides.

    • Si vous faites référence à LinkedList en Java Collection, il est doublement lié et accès rapide à la tête et la queue, de sorte que l'accès au dernier élément prend également en O(1).
    • Accéder dernier élément de la LinkedList est pas O(N). Si vous utilisez descendingIterator(), il est réalisé en O(1). Voir coffeeorientedprogramming.wordpress.com/2018/04/23/... (donc downvote).
    InformationsquelleAutor Piyush Yawalkar