Quelle est la manière la plus rapide de Java collection avec les fonctionnalités de base d'une File d'attente?

Quelle est la manière la plus rapide de la collection en Java?

Je n'ai besoin que les opérations d'ajouter et de supprimer, l'ordre n'est pas important, est égale à celle des éléments n'est pas un problème, rien de plus que d'ajouter et de supprimer est imporant.

Sans limite de taille est trop important.

Ces de collecte vous avez des Objets à l'intérieur de lui.

Actuellement, je suis en utilisant ArrayDeque parce que je vois c'est le plus rapide de la File d'attente de la mise en œuvre.

  • Si l'ordre n'est pas important, vous n'êtes pas à la recherche d'une file d'attente.
  • Actuellement, je suis en ajoutant dans la finale et la récupération depuis le début(comme une File d'attente) , mais si je peux prendre tous les éléments, un par un, je peux utiliser une autre Collection.
  • "...l'optimisation prématurée est la racine de tous les maux"
  • le choix de la collecte de droit n'est pas l'optimisation prématurée.
  • C'est un webcrawler pour un deuxième projet, de sorte que la vitesse est un élément important ici.
  • Si c'est un webcrawler il va être liées au réseau: les performances de la file d'attente va être infondée.
  • Oui, je sais, mais c'est pour mieux garantir que la limite est le réseau et non à ma demande.
  • BoltClock, c'est incorrect pour un capital-Q de la File d'attente en Java. Il signifie seulement "une mutable collection avec un élément de tête". Relire java.util.La file d'attente.

InformationsquelleAutor Renato Dinhani | 2011-05-25
  1. 83

    ArrayDeque est le meilleur. Voir cette référence, qui vient de ce blog sur les résultats de cette analyse comparative. ArrayDeque n'ont pas les frais généraux de nœud allocations LinkedList n'est ni la surcharge de déplacer le contenu du tableau à gauche sur supprimer ArrayList a. Dans l'indice de référence, il effectue sur 3x ainsi que LinkedList pour de grandes files d'attente et même un peu mieux que les ArrayList pour les files d'attente vides. Pour de meilleures performances, vous aurez probablement envie de lui donner une capacité initiale assez grand pour contenir le nombre d'éléments qu'il est susceptible de détenir à la fois pour éviter de nombreux redimensionne.

    Entre ArrayList et LinkedList, il semble que cela dépend de la moyenne de nombre de total des éléments de la file d'attente va contenir à un moment donné et que LinkedList beats ArrayList à partir de 10 éléments.

    • Liste de tableaux utilisés en tant que la pile doit être la même qu'ArrayDeque, la capacité initiale grandement affecter les performances. Trop de moyens, plus de mémoire à allouer et de recueillir, trop peu de moyens pour faire plus de copies (mais imo c'est globalement mieux que de trop grandes pour des boucles serrées). Je ne pouvais pas voir la source de l'indice de référence, est-il disponible?
    • Oui, utilisée comme une pile ArrayList serait à peu près équivalente, si ArrayDeque's javadoc suggère qu'il peut être un peu plus rapide. Et oui, étant donné les exigences de la question, pile-comme l'utilisation marcherait bien. L'indice de référence a été spécifiquement pour la file d'attente FIFO utilisation bien (vous pouvez voir un exemple de code dans les liens blog post).
    • hmm. l'indice de référence est un peu faussée vers LinkedList si (L'intégralité du test s'exécute dans le jeune gen et dans la mémoire cache). ArrayDeque est également de taille correctement (pas de redimensionnement dans la boucle) et la taille reste la même. Je ne peux même pas penser une seule bonne utilisation d'une file d'attente où la file d'attente reste pleine. Mais oui, le resultat attendu. Note de côté: la doc de ArrayDeque listes de java.util.Pile (s'étend Vecteur) à être plus lent pas ArrayList, Cependant, en effet, il peut être mieux que la liste de tableaux puisqu'il n'est pas explicite modCount soutien et de l'explicite pas la gamme des contrôles.
    • Évidemment, c'est souvent le cas que d'une file d'attente n'est pas complète, mais le point de référence est essentiellement à tester la performance d'un seul ajouter et supprimer lorsque la file d'attente est à une gamme de tailles différentes, de sorte qu'il couvre. Aussi, il est raisonnable que le ArrayDeque ne pas redimensionner car d'Une part, le dimensionner correctement est une option dans la vraie utilise et B) redimensionne sera extrêmement rare à long terme de l'utilisation d'une file d'attente. Microbenchmarks ne sera jamais parfait, mais je pense que l'on est assez bonne. Et oui, je n'ai misremember la ArrayDeque javadoc... oups!
    • nul besoin de rappeler les docs, je suppose. Juste pour rappeler que cyclique des tableaux de prendre les meilleures pratiques, les files d'attente, sauf si vous avez besoin d'un lock-libre concurrence. C'est juste une honte la façon dont beaucoup mieux CLQ est que LinkedList.
    • Je me rends compte que cette question est ancienne, mais vos deux liens sont morts. Il y a un autre Url?
    • Désolé, je n'ai aucune idée de l'endroit où vous pourriez trouver. Il se peut que, si vous faites défiler assez loin en arrière sur publicobject.com vous pouvez trouver le blog.
    • Depuis que j'ai eu le même problème que @rath, j'ai rampé le blog original et j'ai trouvé l'article original: https://publicobject.com/2010/07/07/caliper_confirms_reality_linked_list_vs_array_list/. Malheureusement, si j'essaie de voir les résultats de la référence, je reçois un 401 - erreur non autorisée.
    • Voici également une autre expérience qui confirme que ArrayDeque est 3x plus rapide que LinkedList: java-performance.info/linkedlist-performance

    InformationsquelleAutor ColinD
  2. 6

    Vous pouvez utiliser un java.util.LinkedList - il est doublement lié et cicrular, afin d'ajouter à une extrémité, et tenant de l'autre sont en O(1)

    Quelle que soit mise en œuvre que vous choisissez, reportez-vous à la Queue interface, de sorte que vous pouvez facilement le modifier s'il s'avère ne pas l'adapter à votre cas (si, bien sûr, une file d'attente est ce qu'il vous faut en premier lieu)

    Mise à jour: Colin réponse montre un point de repère qui conclut que ArrayDeque est mieux. Les deux ont O(1) opérations, mais LinkedList crée de nouveaux objets (les nœuds), ce qui légèrement les performances. Puisque les deux ont O(1) je ne pense pas que ce serait trop de mal à choisir LinkedList bien.

    • ArrayDeque est objectivement meilleur.
    • J'ai vu, mais pourquoi? En raison de la création de l'objet (les nœuds) dans le linekdlist? Les deux semblent être O(1)
    • Ouais, la création de l'objet dans LinkedList impacts à la fois le temps et les performances de la mémoire.
    • Donc, la matrice de redimensionnement dans ArrayDeque. La réelle prise en compte ici est la complexité algorithmique. En ce qui concerne un tableau est O(N) pour ajouter/supprimer, en ce qui concerne les liens de est O(1).
    • O(1) pour ajouter et supprimer à l'avant/à la fin (c'est à dire lorsqu'il est utilisé comme une file d'attente ou la pile) parce que c'est un tableau circulaire et de ne pas copier quoi que ce soit dans ces cas. En outre, redimensionner est une opération occasionnelle qui peut souvent être évité avec une capacité initiale. LinkedList's, de frais généraux supplémentaires de création de l'objet (en plus de la collecte des ordures de cet objet) affecte à chaque ajout/suppression de dans la file d'attente. Le test j'ai fait un lien se montre toujours 3x plus rapide qu'un LinkedList.
    • Oui je vois merci.
    • pouvez-vous expliquer exactement comment il est O(1) pour les supprimer? vous à la parcourir pour trouver l'élément à supprimer et d'itération d'une LinkedList est terrible. Liste de tableaux et ArrayDeque sont un amorti O(1) pour ajoute, rien de tel que O(n).
    • Il est O(1) pour supprimer en supposant que vous êtes déjà à l'élément à supprimer. La déclaration est à partir de la Javadoc.
    • En Plus des tableaux de toujours surpasser les listes liées pour une grande quantité de petits objets en raison de défauts de cache sur les processeurs. Les listes chaînées sont généralement disjoints dans la mémoire , qui n'est pas le cas avec les tableaux.
    • O(1) != O(1). O() est juste une mesure de complexité, pas de temps d'exécution. Une opération qui prend toujours 5 ans, peu importe le n est O(1), comme c'est une opération qui prend toujours 5 mme. Je préfère utiliser celui qui prend 5 mme. Même une opération qui prend 5 ms par élément (qui est O(n)) va être mieux que la 5 année, l'opération si n ne soit pas trop grand.
    • personne ne remet en que. Et ma mise à jour indique que le O(1) dans l'un des cas est plus rapide. Mais compte tenu de la relative similitude entre les opérations, O-notation est une indication de la vitesse, même si elle correspond à la complexité.

    InformationsquelleAutor Bozho