Es ist klar, dass die Suchleistung der generischen HashSet<T>
Klasse höher ist als die der generischen List<T>
Klasse. Vergleichen Sie einfach den Hash-basierten Schlüssel mit dem linearen Ansatz in der List<T>
Klasse.
Das Berechnen eines Hash-Schlüssels kann jedoch selbst einige CPU-Zyklen dauern, sodass für eine kleine Anzahl von Elementen die lineare Suche eine echte Alternative zum sein kann HashSet<T>
.
Meine Frage: Wo ist die Gewinnschwelle?
Um das Szenario zu vereinfachen (und fair zu sein), nehmen wir an, dass die List<T>
Klasse die Equals()
Methode des Elements verwendet, um ein Element zu identifizieren.
.net
performance
collections
list
hash
Michael Damatov
quelle
quelle
Antworten:
Viele Leute sagen, dass, sobald Sie die Größe erreicht haben, in der Geschwindigkeit tatsächlich ein Problem ist,
HashSet<T>
das immer schlagen wirdList<T>
, aber das hängt davon ab, was Sie tun.Angenommen, Sie haben eine
List<T>
, die immer nur durchschnittlich 5 Artikel enthält. Wenn in einer großen Anzahl von Zyklen in jedem Zyklus ein einzelnes Element hinzugefügt oder entfernt wird, ist es möglicherweise besser, a zu verwendenList<T>
.Ich habe dies auf meiner Maschine getestet, und es muss sehr, sehr klein sein, um einen Vorteil daraus zu ziehen
List<T>
. Bei einer Liste mit kurzen Zeichenfolgen verschwand der Vorteil nach Größe 5, bei Objekten nach Größe 20.Hier sind diese Daten als Grafik dargestellt:
Hier ist der Code:
quelle
List<T>
Spiel-Engine hinzugefügt und entfernt werden kann , und da ich normalerweise ein hohes Volumen an Objekten habe, wäre diese Art von Sammlung perfekt.Du siehst das falsch an. Ja, eine lineare Suche in einer Liste schlägt ein HashSet für eine kleine Anzahl von Elementen. Bei so kleinen Sammlungen spielt der Leistungsunterschied normalerweise keine Rolle. Es sind im Allgemeinen die großen Sammlungen, über die Sie sich Sorgen machen müssen, und hier denken Sie in Bezug auf Big-O . Wenn Sie jedoch einen echten Engpass bei der HashSet-Leistung gemessen haben, können Sie versuchen, eine hybride Liste / HashSet zu erstellen. Dazu führen Sie jedoch viele empirische Leistungstests durch, ohne Fragen zur SO zu stellen.
quelle
when small collection becomes large enough to worry about HashSet vs List?
Zehntausenden, Milliarden von Elementen neu definieren.HashSet<T>
. In Fällen mit geringer Anzahl, in denen dieList<T>
Geschwindigkeit möglicherweise höher ist, ist der Unterschied unbedeutend . "Es ist im Wesentlichen sinnlos, zwei Strukturen für eine Leistung zu vergleichen , die sich unterschiedlich verhalten. Verwenden Sie die Struktur, die die Absicht vermittelt. Selbst wenn Sie sagen, dass Sie
List<T>
keine Duplikate haben würden und die Iterationsreihenfolge keine Rolle spielt, ist esHashSet<T>
immer noch eine schlechte Wahl,List<T>
da es relativ weniger fehlertolerant ist.Trotzdem werde ich einige andere Aspekte der Leistung untersuchen.
Obwohl die Addition in beiden Fällen O (1) ist, ist sie in HashSet relativ langsamer, da die Kosten für die Vorberechnung von Hash-Code vor dem Speichern anfallen.
Die überlegene Skalierbarkeit von HashSet hat Speicherkosten. Jeder Eintrag wird zusammen mit seinem Hash-Code als neues Objekt gespeichert. Dieser Artikel könnte Ihnen eine Idee geben.
quelle
Ob Sie ein HashSet <> oder eine Liste <> verwenden, hängt davon ab, wie Sie auf Ihre Sammlung zugreifen müssen . Wenn Sie die Reihenfolge der Artikel garantieren müssen, verwenden Sie eine Liste. Wenn Sie dies nicht tun, verwenden Sie ein HashSet. Lassen Sie Microsoft sich Gedanken über die Implementierung ihrer Hashing-Algorithmen und -Objekte machen.
Ein HashSet greift auf Elemente zu, ohne die Sammlung aufzählen zu müssen (Komplexität von O (1) oder in der Nähe davon). Da eine Liste im Gegensatz zu einem HashSet die Reihenfolge garantiert, müssen einige Elemente aufgelistet werden (Komplexität von O (n)).
quelle
List
wird a bevorzugt, da Sie sich an einen Index erinnern können - das ist die Situation, in der Sie sich befinden beschreiben.Ich dachte nur, ich würde einige Benchmarks für verschiedene Szenarien verwenden, um die vorherigen Antworten zu veranschaulichen:
Und für jedes Szenario nach Werten suchen, die angezeigt werden:
Vor jedem Szenario habe ich zufällig große Listen mit zufälligen Zeichenfolgen erstellt und dann jede Liste einem Hashset zugeführt. Jedes Szenario lief 10.000 Mal, im Wesentlichen:
(Testpseudocode)
Beispielausgabe
Getestet unter Windows 7, 12 GB RAM, 64 Bit, Xeon 2,8 GHz
quelle
List
immer noch nur 0,17 Millisekunden für die Durchführung einer einzelnen Suche benötigt werden und wahrscheinlich keine Substitution erforderlich ist,HashSet
bis die Suchfrequenz absurde Werte erreicht. Bis dahin ist die Verwendung von List normalerweise das geringste Problem.Die Gewinnschwelle hängt von den Kosten für die Berechnung des Hash ab. Hash-Berechnungen können trivial sein oder nicht ... :-) Es gibt immer die System.Collections.Specialized.HybridDictionary-Klasse, damit Sie sich keine Sorgen um die Gewinnschwelle machen müssen.
quelle
Die Antwort lautet wie immer: " Es kommt darauf an ". Ich gehe von den Tags aus, von denen Sie sprechen, C #.
Ihre beste Wette ist zu bestimmen
und schreibe einige Testfälle.
Dies hängt auch davon ab, wie Sie die Liste sortieren (falls überhaupt sortiert), welche Art von Vergleichen durchgeführt werden müssen, wie lange der Vorgang "Vergleichen" für das bestimmte Objekt in der Liste dauert oder sogar, wie Sie die Liste verwenden möchten Sammlung.
Im Allgemeinen hängt die beste Auswahl nicht so sehr von der Größe der Daten ab, mit denen Sie arbeiten, sondern vielmehr davon, wie Sie darauf zugreifen möchten. Haben Sie jedes Datenelement mit einer bestimmten Zeichenfolge oder anderen Daten verknüpft? Eine Hash-basierte Sammlung wäre wahrscheinlich am besten. Ist die Reihenfolge der Daten, die Sie speichern, wichtig, oder müssen Sie gleichzeitig auf alle Daten zugreifen? Eine reguläre Liste kann dann besser sein.
Zusätzlich:
In meinen obigen Kommentaren wird natürlich davon ausgegangen, dass "Leistung" Datenzugriff bedeutet. Noch etwas zu beachten: Wonach suchen Sie, wenn Sie "Leistung" sagen? Ist Leistung individueller Wert nachschlagen? Ist es die Verwaltung großer (10000, 100000 oder mehr) Wertesätze? Ist es die Leistung, die Datenstruktur mit Daten zu füllen? Daten entfernen? Zugriff auf einzelne Datenbits? Werte ersetzen? Über die Werte iterieren? Speichernutzung? Datenkopiergeschwindigkeit? Wenn Sie beispielsweise über einen Zeichenfolgenwert auf Daten zugreifen, Ihre Hauptleistungsanforderung jedoch eine minimale Speichernutzung ist, können widersprüchliche Entwurfsprobleme auftreten.
quelle
Sie können ein HybridDictionary verwenden, das die Bruchstelle automatisch erkennt und Nullwerte akzeptiert, sodass es im Wesentlichen mit einem HashSet identisch ist.
quelle
Es hängt davon ab, ob. Wenn die genaue Antwort wirklich wichtig ist, führen Sie eine Profilerstellung durch und finden Sie es heraus. Wenn Sie sicher sind, dass Sie nie mehr als eine bestimmte Anzahl von Elementen im Set haben, wählen Sie eine Liste. Wenn die Anzahl unbegrenzt ist, verwenden Sie ein HashSet.
quelle
Kommt darauf an, was du hasst. Wenn Ihre Schlüssel Ganzzahlen sind, benötigen Sie wahrscheinlich nicht sehr viele Elemente, bevor das HashSet schneller ist. Wenn Sie eine Zeichenfolge eingeben, ist sie langsamer und hängt von der Eingabezeichenfolge ab.
Sicherlich könnten Sie ziemlich einfach einen Benchmark erstellen?
quelle
Ein Faktor, den Sie nicht berücksichtigen, ist die Robustheit der GetHashcode () -Funktion. Mit einer perfekten Hash-Funktion bietet das HashSet eindeutig eine bessere Suchleistung. Wenn sich die Hash-Funktion verringert, verringert sich auch die HashSet-Suchzeit.
quelle
Hängt von vielen Faktoren ab ... Listenimplementierung, CPU-Architektur, JVM, Schleifensemantik, Komplexität der Equals-Methode usw. Mit der Zeit wird die Liste groß genug, um eine Hash-basierte Binärdatei (1000+ Elemente) effektiv zu bewerten Lookups schlagen lineare Suchvorgänge zweifellos, und der Unterschied vergrößert sich nur von dort aus.
Hoffe das hilft!
quelle