HashSet vs ArrayList contient de la performance

Lors du traitement de grandes quantités de données, il m'arrive souvent de faire ce qui suit:

HashSet<String> set = new HashSet<String> ();
//Adding elements to the set
ArrayList<String> list = new ArrayList<String> (set);

Quelque chose comme "dumping" le contenu de l'ensemble de la liste. J'ai l'habitude de le faire depuis les éléments que j'ai souvent tendance à contenir des doublons je veux supprimer, et cela semble être un moyen facile de les supprimer.

Uniquement avec cet objectif à l'esprit (éviter les doublons), je pourrais aussi écrire:

ArrayList<String> list = new ArrayList<String> ();
//Processing here
if (! list.contains(element)) list.add(element);
//More processing here

Et donc pas besoin de "dumping", l'ensemble sur la liste. Cependant, j'aimerais faire une petite vérification avant l'insertion de chaque élément (que je suis en supposant que HashSet ne)

Est l'une des deux possibilités nettement plus efficace?

Vous avez votre première partie de la question mal. Vous êtes dumping liste dans le jeu pour éliminer les doublons, et non pas l'inverse, non?
Pourquoi ne pas le tester? Btw, pourquoi s'embêter avec la conversion de l'ensemble dans une liste, de toute façon? En passant par le réglage le plus probablement à être plus rapide pour les grands tableaux.
Salut, merci pour vos commentaires. Dans ce scénario, je remplir mon set avec les données (pour éviter les doublons) et puis vidage à une liste, de cette façon je peux obtenir une Liste avec les pas dupes. Si je n'ai pas besoin de la liste je ne voudrais pas créer réellement un, mais parfois, un tri est appliqué par la suite, et une partie du code que je travaille avec nécessite des listes.

OriginalL'auteur Jorge | 2015-09-13

44

L'ensemble donnera de bien meilleures performances (O(n) vs O(n^2) pour la liste), et c'est normal parce que l'appartenance (le contains opération) est le très fins d'un ensemble.

Contient un HashSet est O(1) par rapport à O(n) pour une liste, par conséquent, vous ne devez jamais utiliser une liste si vous avez souvent besoin d'exécuter contains.

Si la liste ne contient que quelques éléments?
La complexité de calcul ne s'applique pas à délimitée problèmes. Son objectif est de comprendre comment beaucoup plus lente, le calcul devient lorsque la taille du problème augmente, devient infiniment grand. Cela dit, je ne pense pas qu'il y a toujours un avantage à l'aide d'une liste de plus d'un hachage ensemble pour la contains opération. Bien sûr, un ensemble, a une plus grande charge de la mémoire en général, mais si vous avez quelques éléments seulement pourquoi voudriez-vous même des soins ? Plus efficace de l'ensemble des implémentations existent pour délimité les ensembles de données (EnumSet par exemple), mais en général, une simple hachage doit être que suffisant pour les exigences de performance
Souvent, nous avons déjà une éphémère de la liste pour laquelle nous avons besoin pour exécuter .contains. La question est de savoir à partir de quelle taille est-il judicieux de créer un Jeu? Moins de 10 éléments à la fois effectuer sur l'échelle de 1 à 2 micros, mais nous passons du temps pour créer un Jeu. De toute façon, ici, c'est rapide référence si quelqu'un intéressé gist.github.com/ibalashov/0138e850e58942569a636dffa75f0bb9
pour être exact, c'est amortis O(1). Cela a peu à voir avec les doublons si, List::contains s'arrête à la première double de toute façon, c'est plus sur le hashing structure de HashSet ici qui donne beaucoup d'un coup de pouce
Je fais de temps en temps pour les gens que j'ai aimé leurs réponses pendant un certain jour, si cela ne vous dérange pas 🙂

OriginalL'auteur Dici
8

La ArrayList utilise un tableau pour stocker les données. Le ArrayList.contains sera de O(n) la complexité. Donc, essentiellement, de la recherche dans la gamme de nouveau et de nouveau devra O(n^2) complexité.

Tout HashSet utilise le mécanisme de hachage pour stocker les éléments dans leurs seaux. L'opération de HashSet sera plus rapide pour une longue liste de valeurs. Il atteindra l'élément O(1).

OriginalL'auteur YoungHobbit
4

J'ai fait un test merci de vérifier le résultat:

Pour les MÊMES éléments de CHAÎNE dans un HashSet, TreeSet, ArrayList et LinkedList, voici les résultats pour
1. 50.000 Uuid
  - ÉLÉMENT RECHERCHÉ : e608c7d5-c861-4603-9134-8c636a05a42b (indice de 25.000)
  - hashSet.contient(point) ? VRAI 0 ms
  - treeSet.contient(point) ? VRAI 0 ms
  - arrayList.contient(point) ? VRAI 2 ms
  - linkedList.contient(point) ? VRAI 3 ms
2. 5.000.000 Uuid
  - ÉLÉMENT RECHERCHÉ : 61fb2592-3186-4256-a084-6c96f9322a86 (indice de 25.000)
  - hashSet.contient(point) ? VRAI 0 ms
  - treeSet.contient(point) ? VRAI 0 ms
  - arrayList.contient(point) ? VRAI 1 ms
  - linkedList.contient(point) ? VRAI 2 ms
3. 5.000.000 Uuid
  - ÉLÉMENT RECHERCHÉ : db568900-c874-46ba-9b44-0e1916420120 (indice de 2.500.000)
  - hashSet.contient(point) ? VRAI 0 ms
  - treeSet.contient(point) ? VRAI 0 ms
  - arrayList.contient(point) ? VÉRITABLE 33 ms
  - linkedList.contient(point) ? VÉRITABLE 65 ms
Basé sur les résultats ci-dessus, il n'y a PAS beaucoup de différence de l'aide du tableau de la liste de vs. Peut-être que vous pouvez essayer de modifier ce code et remplacer les Chaîne avec votre Objet et de voir les différences, puis...
```
    public static void main(String[] args) {
Set<String> hashSet = new HashSet<>();
Set<String> treeSet = new TreeSet<>();
List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();
List<String> base = new ArrayList<>();
for(int i = 0; i<5000000; i++){
if(i%100000==0) System.out.print(".");
base.add(UUID.randomUUID().toString());
}
System.out.println("\nBase size : " + base.size());
String item = base.get(25000);
System.out.println("SEARCHED ITEM : " + item);
hashSet.addAll(base);
treeSet.addAll(base);
arrayList.addAll(base);
linkedList.addAll(base);
long ms = System.currentTimeMillis();
System.out.println("hashSet.contains(item) ? " + (hashSet.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
System.out.println("treeSet.contains(item) ? " + (treeSet.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
System.out.println("arrayList.contains(item) ? " + (arrayList.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
System.out.println("linkedList.contains(item) ? " + (linkedList.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
}
```
"Basé sur les résultats ci-dessus, il n'y a PAS une GRANDE différence à l'aide de la liste des ensembles vs". À partir de votre nombre, c'est clairement pas le cas; pour 5 millions d'Uuid, une ArrayList est au moins 33x plus lent que ce soit un TreeSet ou un HashSet lorsque l'élément est dans le milieu de la Collection.
Cette référence est trop petite pour être concluante, et votre interprétation de ce qu'il montre est incorrecte comme mentionné par abhi.

OriginalL'auteur urs86ro
3

Si vous n'avez pas besoin d'une liste, je voudrais juste utiliser un Ensemble et c'est le naturel de la collection à utiliser si l'ordre n'a pas d'importance et que vous souhaitez ignorer les doublons.

Vous pouvez faire les deux est que vous devez une Liste sans doublons.
```
private Set<String> set = new HashSet<>();
private List<String> list = new ArrayList<>();
public void add(String str) {
if (set.add(str))
list.add(str);
}
```
Cette façon, la liste ne contiendra que des valeurs uniques, l'original de l'ordre d'insertion est préservée et l'opération est O(1).

Je tiens à mentionner que d'un LinkedHashSet pourrait être utilisé si l'ordre des questions, ou un TreeSet si il y a un ordre de tri exigence
Tellement simple et tellement élégant! Me gusta!
remarque: Définissez.ajouter(x) ne renvoie true si elle a été ajoutée pour la première fois.

OriginalL'auteur Peter Lawrey

Vous pouvez ajouter des éléments à la liste elle-même.
Puis, à dedup -

HashSet<String> hs = new HashSet<>(); //new hashset
hs.addAll(list); //add all list elements to hashset (this is the dedup, since addAll works as a union, thus removing all duplicates)
list.clear(); //clear the list
list.addAll(hs); //add all hashset elements to the list

Si vous avez juste besoin d'un jeu avec dedup, vous pouvez également utiliser le addAll() sur un ensemble différent, de sorte qu'elle ne contient que des valeurs uniques.

OriginalL'auteur Prateek Paranjpe

Vous devez vous connecter pour publier un commentaire.