Java collection d'insertion: Ensemble contre la Liste

Je suis en train de penser sur la façon de remplir une collection avec une grande quantité d'objets uniques.
Comment est le coût d'une insertion dans un Ensemble (disons HashSet) par rapport à une Liste (dire ArrayList)?

Mon sentiment est que le double élimination dans des ensembles peut causer une légère surcharge.

Si vous avez déjà un mécanisme qui garantit l'unicité pourquoi s'embêter avec le jeu? Si vous n'avez pas et vous avez besoin de garantir l'unicité, puis une liste n'est certainement pas ce que vous voulez.

OriginalL'auteur Will | 2011-05-18

  1. 10

    Il n'y a pas de "double élimination" telles que la comparaison de tous les éléments existants. Si vous insérez dans hachage ensemble, c'est vraiment un dictionnaire d'éléments par le code de hachage. Il n'y a pas de vérification des doublons, sauf si il y a déjà les éléments avec le même code de hachage. Dans des limites raisonnables (bien distribué) fonction de hachage, c'est pas si mal que ça.

    Comme l'a fait remarquer, en raison du dictionnaire de la structure de HashSet est probablement un peu plus lent que d'une ArrayList (sauf si vous souhaitez insérer "entre" les éléments existants). C'est un peu plus grande. Je ne suis pas sûr que c'est une différence importante cependant.

    La double élimination est là, c'est juste inhérente à la structure de données.
    La droite. Je veux dire, il n'est généralement pas de double élimination qui serait toujours comparer le nouveau élément inséré à ceux existants déjà (à moins que vous foiré la hashCode).
    Merci pour la clarification. Encore de l'insertion dans une liste est donc un tout petit peu moins cher sur le plan conceptuel, à droite?

    OriginalL'auteur Konrad Garus

  2. 3

    Vous avez raison: l'ensemble des structures sont par nature plus complexes dans le but de reconnaître et d'éliminer les doublons. Si cette surcharge est importante pour votre cas doit être testé avec un indice de référence.

    Un autre facteur est l'utilisation de la mémoire. Si vos objets sont très petites, la surcharge de la mémoire présenté par l'ensemble de la structure peut être importante. Dans le cas le plus extrême (TreeSet<Integer> vs ArrayList<Integer>) l'ensemble de la structure peut nécessiter plus de 10 fois plus de mémoire.

    OriginalL'auteur Michael Borgwardt

  3. 3

    Si vous êtes certains vos données seront uniques, l'utilisation d'une Liste. Vous pouvez utiliser un Ensemble de appliquer cette règle.

    Les ensembles sont plus rapides que les Listes de si vous avez un grand ensemble de données, tandis que le inverse est vrai pour les petits ensembles de données. Je n'ai pas personnellement testé cette affirmation.

    Le type de Liste?

    Pensez également à la Liste à utiliser. LinkedLists sont plus rapides lors de l'ajout, de la suppression des éléments.

    ArrayLists sont plus rapides à accès aléatoire (for boucles, etc), mais cela peut être contourné en utilisant le Iterator d'une LinkedList. ArrayLists sont beaucoup plus vite à: list.toArray().

    Pas sûr que les listes chaînées sont rapides pour l'insertion... Pensé qu'il était temps O(n) le temps de recherche de la position, puis constant (et faible) pour l'insertion elle-même. LinkedList ne fournissent pas un accès aléatoire aux données. En outre, un itérateur n' pas fournir un accès aléatoire.
    En réalité, je soupçonne tout dépend de la mise en œuvre, et les OP peuvent facilement créer leurs propres. La Liste et Définir les interfaces évidemment fournir aucun code, donc on peut être faite plus rapidement que les autres. Cela dit, je ne suis pas sûr de savoir comment, mais j'ai été très impressionné par LinkedList, et échangé après j'ai trouvé ArrayList d'être trop lent. Je faisais add() et itération
    C'est à cause de la structure de la LinkedList, et parce que vous avez régulièrement besoin de faire un tableau de copie lors de l'utilisation d'ajouter sur une liste de tableaux. LinkedLists sont vraiment efficace pour les insertions au début ou à la fin, mais certainement pas pour un accès aléatoire. Les Insertions ne sont pas limités à des opérations d'ajout.
    Merci beaucoup. J'ai supprimé la référence à l'insertion pour LinkedLists dans ma réponse ci-dessus
    Les liens ne fonctionne pas pour moi

    OriginalL'auteur Redandwhite

  4. 2

    Si le but est l'unicité des éléments, vous devez utiliser une mise en œuvre de la java.util.Ensemble interface. La classe java.util.HashSet et java.util.LinkedHashSet ont O(alpha) (à proximité de O(1) dans le meilleur des cas) de la complexité pour insérer, supprimer et contient vérifier.

    ArrayList ont O(n) pour l'objet (pas d'index) contient vérifier (que vous avez à faire défiler toute la liste) et d'insertion (si l'insertion n'est pas en queue de la liste, vous devez modifier l'ensemble de souligner tableau).

    Vous pouvez utiliser LinkedHashSet qui conserve l'ordre d'insertion et ont la même potentialité de HashSet (seulement un peu plus de mémoire).

    Les listes n'ont pas d'insertion frais de O(n)
    ArrayList oui, parce que le tableau doit être décalée. Dans le pire des cas (insertion dans l'index 0), tous les éléments du tableau doivent être décalés par 1.

    OriginalL'auteur Alberto

  5. 1

    Vous devez comparer des implémentations concrètes (par exemple HashSet avec ArrayList), parce que les interfaces abstraites Set/List n'ont pas vraiment vous dire quelque chose à propos de la performance.

    De l'insertion dans une HashSet est une jolie opération pas cher, aussi longtemps que le hashCode() de l'objet à insérer est sain d'esprit. Il sera toujours légèrement plus lent que ArrayList, parce que c'est de l'insertion est une simple insertion dans un tableau (en supposant que vous insérez dans la fin et il y a encore de l'espace libre; je n'ai pas de facteur de redimensionnement du tableau interne, parce que le même coût s'applique à HashSet).

    OriginalL'auteur Joachim Sauer

  6. 1

    Je ne pense pas que vous pouvez faire ce jugement simplement sur le coût de construction de la collection. D'autres choses que vous devez prendre en compte sont:

    • Est le jeu de données d'entrée commandé? Est-il nécessaire que les données de sortie de la structure conserve l'ordre d'insertion?
    • Est-il nécessaire que les données de sortie de la structure est ordonnée (ou réorganisés) basé sur les valeurs d'élément?
    • Sera la sortie de la structure de données d'être modifié par la suite? Comment?
    • Est-il nécessaire que les données de sortie de la structure est en double gratuit si d'autres éléments sont ajoutés par la suite?
    • Savez-vous combien d'éléments sont susceptibles de l'être dans le jeu de données en entrée?
    • Pouvez-vous mesurer la taille du jeu de données d'entrée? (Ou il est fourni via un itérateur?)
    • Ne l'utilisation de l'espace de la matière?

    De tous ces effets de votre choix de la structure de données.

    OriginalL'auteur Stephen C

  7. 1

    Java Liste:

    Si vous n'avez pas une telle exigence que vous devez garder en double ou pas. Ensuite, vous pouvez utiliser la Liste au lieu de Set.

    Liste est une interface dans le cadre de Collecte. Qui s'étend de la Collection de l'interface. et ArrayList, LinkedList est la mise en œuvre de la Liste de l'interface.

    Quand utiliser ArrayList ou LinkedList

    ArrayList: Si vous avez une telle exigence dans votre application pour la plupart des travaux est de l'accès aux données. Alors vous devriez aller pour ArrayList. parce que ArrayList implémente RtandomAccess de l'interface qui est un Marqueur de l'Interface. en raison de Marqueur de l'interface liste de tableaux ont la capacité d'accéder aux données en temps O(1) fois. et vous pouvez utiliser la liste de tableaux sur LinkedList où vous souhaitez obtenir des données selon l'ordre d'insertion.

    LinkedList: Si vous avez une telle exigence que votre fonctionnent la plupart du temps est l'insertion ou de la suppression. Ensuite, vous devez utiliser LinkedList sur la liste de tableaux. parce que dans LinkedList l'insertion et la suppression arriver en O(1), tandis que dans ArrayList il est O(n) fois.

    Java Jeu:

    Si vous avez des exigences de votre application que vous ne voulez pas de doublons. Alors vous devriez aller pour Définir la place de la Liste. Parce que l'Ensemble ne stocke pas de doublons. Parce que l'Ensemble fonctionne sur le principe du Hachage. Si l'on ajoute l'objet de Définir puis d'abord, il vérifie l'objet hashCode dans le seau si c'est de trouver tout hashCode présents dans il est allé à contre-courant, puis il va pas ajouter cet objet.

    OriginalL'auteur Vpn_talent