HashSet vs Arraylist enthält Performance

Wenn große Datenmengen verarbeiten ich finde mich oft die folgenden Schritte ausführen:HashSet vs Arraylist enthält Performance

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

So etwas wie „Dumping“ den Inhalt des Satzes in der Liste. Normalerweise mache ich das, weil die Elemente, die ich hinzufüge, oft Duplikate enthalten, die ich entfernen möchte, und dies scheint eine einfache Möglichkeit zu sein, sie zu entfernen.

Mit nur diesem Ziel vor Augen (Vermeidung von Dubletten) Ich könnte auch schreiben:

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

Und somit keine Notwendigkeit für den Satz in die Liste „Dumping“. Ich würde jedoch einen kleinen Haken machen, bevor ich jedes Element einfüge (was ich auch für HashSet halte)

Ist eine der beiden Möglichkeiten deutlich effizienter?

Quelle

2015-09-13 Jorge

Sie haben Ihren ersten Teil der Frage falsch. Du legst die Liste im Set ab, um Duplikate loszuwerden, nicht umgekehrt, oder? – MirMasej

Warum testest du es nicht? Übrigens warum sollte ich das Set sowieso in eine Liste umwandeln? Das Durchlaufen von Set wird für große Arrays höchstwahrscheinlich schneller sein. – luk32

Hallo, danke für deine Kommentare. In diesem Szenario befülle ich mein Set mit den Daten (um Duplikate zu vermeiden) und lege es dann in eine Liste, auf diese Weise erhalte ich effektiv eine Liste ohne Duplikate. Wenn ich die Liste nicht brauchte, würde ich sie nicht erstellen, aber manchmal wird eine Sortierung angewendet, und ein Teil des Codes, mit dem ich arbeite, erfordert Listen. – Jorge

Das Set wird eine deutlich bessere Leistung (O(n) vs O(n^2) für die Liste) geben, und das ist normal, weil Duplikate vermieden werden der Zweck eines Satzes ist.

Enthält für eine HashSet ist O(1) im Vergleich zu O(n) für eine Liste, deshalb sollten Sie nie eine Liste verwenden, wenn Sie oft contains ausführen müssen.

Quelle

2015-09-13 17:11:56 Dici

Was ist, wenn die Liste nur ein paar Elemente enthält? –

Komplexitätsberechnung trifft nicht wirklich auf begrenzte Probleme zu. Sein Ziel ist es zu verstehen, wie viel langsamer die Berechnung wird, wenn die Problemgröße zunimmt und unendlich groß wird. Das heißt, ich glaube nicht, dass es jemals einen Vorteil bei der Verwendung einer Liste über einen Hash-Satz für die 'enthält' Operation gibt. Sicher, ein Set hat im Allgemeinen einen größeren Speicheraufwand, aber wenn Sie nur ein paar Elemente haben, warum kümmern Sie sich überhaupt darum? Es gibt effizientere Set-Implementierungen für beschränkte Datasets (z. B. "EnumSet"), aber im Allgemeinen sollte ein einfacher Hash-Satz für typische Leistungsanforderungen ausreichen. – Dici

Oft haben wir bereits eine ephemere Liste, für die wir '.contains' ausführen müssen. Die Frage ist, ab welcher Größe ist es sinnvoll ein Set zu erstellen? Unter 10 Elementen arbeiten beide auf der Skala von 1-2 Mikros, aber wir verbringen Zeit, um ein Set zu erstellen. Wie auch immer, hier ist eine schnelle Benchmark, wenn jemand interessiert https://gist.github.com/ibalashov/0138e850e58942569a636dffa75f0bb9 –

Die ArrayList verwendet ein Array zum Speichern der Daten. Die wird von O (n) -Komplexität sein. Also im Wesentlichen immer wieder in Array suchen wird O(n^2) Komplexität haben.

Während HashSet verwendet Hash-Mechanismus zum Speichern der Elemente in ihren jeweiligen Eimern. Die Operation von HashSet wird für lange Liste von Werten schneller sein. Es wird das Element in O(1) erreichen.

Quelle

2015-09-13 17:11:47 YoungHobbit

Wenn Sie keine Liste benötigen, würde ich einfach ein Set verwenden. Dies ist die natürliche Sammlung, wenn die Reihenfolge keine Rolle spielt und Duplikate ignoriert werden sollen.

Sie können beides tun, wenn Sie eine Liste ohne Duplikate benötigen.

private Set<String> set = new HashSet<>(); 
private List<String> list = new ArrayList<>(); 


public void add(String str) { 
    if (set.add(str)) 
     list.add(str); 
}

Auf diese Weise enthält die Liste nur eindeutige Werte, die ursprüngliche Reihenfolge bleibt erhalten und die Operation ist O (1).

Quelle

2015-09-13 17:12:07

Ich würde erwähnen, als ein 'LinkedHashSet' könnte verwendet werden, wenn die Reihenfolge von Bedeutung ist, oder ein' TreeSet', wenn es eine Sortierreihenfolge gibt Anforderung – Dici

So einfach und so elegant! Gefällt mir! – Jorge

@Jorge Anmerkung: Set.add (x) gibt nur true zurück, wenn es zum ersten Mal hinzugefügt wurde. –

Sie können der Liste Elemente hinzufügen. Dann 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

Wenn Sie nur einen Satz mit dedup benötigen, können Sie auch den addAll() auf einem anderen Satz verwenden, so dass es nur eindeutige Werte haben.

Quelle

2018-03-08 05:06:53

HashSet vs Arraylist enthält Performance

Antwort

Verwandte Themen