HashSet vs. List-Leistung

405

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.

Michael Damatov
quelle
7
Wenn Sie die Suchzeit wirklich minimieren möchten, sollten Sie auch Arrays und sortierte Arrays berücksichtigen. Um diese Frage richtig zu beantworten, ist ein Benchmark erforderlich, aber Sie müssen uns mehr über T erzählen. Außerdem kann die HashSet-Leistung durch die Laufzeit von T.GetHashCode () beeinflusst werden.
Eldritch Conundrum

Antworten:

819

Viele Leute sagen, dass, sobald Sie die Größe erreicht haben, in der Geschwindigkeit tatsächlich ein Problem ist, HashSet<T>das immer schlagen wird List<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 verwenden List<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.

1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms

2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms

3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms

4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms

5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms

6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms

7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms

8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms

9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms

1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms

4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms

7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms

10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms

13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms

16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms

19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms

22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms

25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms

28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms

31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms

34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms

37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms

40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms

43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms

46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms

49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms

Hier sind diese Daten als Grafik dargestellt:

Geben Sie hier die Bildbeschreibung ein

Hier ist der Code:

static void Main(string[] args)
{
    int times = 10000000;


    for (int listSize = 1; listSize < 10; listSize++)
    {
        List<string> list = new List<string>();
        HashSet<string> hashset = new HashSet<string>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add("string" + i.ToString());
            hashset.Add("string" + i.ToString());
        }

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove("string0");
            list.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");


        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove("string0");
            hashset.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }


    for (int listSize = 1; listSize < 50; listSize+=3)
    {
        List<object> list = new List<object>();
        HashSet<object> hashset = new HashSet<object>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add(new object());
            hashset.Add(new object());
        }

        object objToAddRem = list[0];

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove(objToAddRem);
            list.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");



        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove(objToAddRem);
            hashset.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }

    Console.ReadLine();
}
innominate227
quelle
8
Ich danke dir sehr! Dies ist eine großartige Erklärung. Ich suchte nach etwas, das schneller als eine 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.
Redcodefinal
17
Es gibt tatsächlich eine Sammlung im .NET Framework, die abhängig von der Anzahl der darin enthaltenen Elemente zwischen einer Liste und einer hastierbaren Implementierung wechselt: HybridDictionary .
MgSam
8
MS scheint seinen Gedanken aufgegeben zu haben, da nur eine nicht generische Version verfügbar ist.
MgSam
47
So vollständig diese Antwort auch ist, sie kann die ursprüngliche Frage bezüglich der Suchleistung von Liste und Hashset nicht beantworten. Sie testen, wie schnell Sie sie einfügen und daraus entfernen können. Dies erfordert erheblich mehr Zeit und andere Leistungsmerkmale als die Suche. Versuchen Sie es erneut mit .Contains, und Ihr Diagramm ändert sich erheblich.
Robert McKee
5
@hypehuman Die CPU kann nicht direkt mit Daten im Systemspeicher arbeiten, sondern zieht Daten aus dem Speicher in den Cache, um sie zu bearbeiten. Es gibt eine erhebliche Verzögerung zwischen der Anforderung zum Verschieben des Speichers und dem tatsächlich eintreffenden Speicher, sodass die CPU häufig die gleichzeitige Verschiebung eines größeren Teils des zusammenhängenden Speichers anfordert. Die Idee dahinter ist, dass der für den nächsten Befehl benötigte Speicher wahrscheinlich sehr nahe an dem vom vorherigen Befehl verwendeten Speicher liegt und sich daher häufig bereits im Cache befindet. Wenn Ihre Daten über den gesamten Speicher verteilt sind, verringert sich die Wahrscheinlichkeit, Glück zu haben.
Roy T.
70

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.

Eloff
quelle
5
große Sammlungen, über die Sie sich Sorgen machen müssen . Wir können diese Frage in when small collection becomes large enough to worry about HashSet vs List?Zehntausenden, Milliarden von Elementen neu definieren.
Om-Nom-Nom
8
Nein, Sie werden einen erheblichen Leistungsunterschied über einigen hundert Elementen feststellen. Der Punkt ist immer, ein HashSet zu verwenden, wenn Sie die Arten von Zugriffen ausführen, für die HashSet gut ist (z. B. Element X in der Gruppe). Wenn Ihre Sammlung so klein ist, dass eine Liste schneller ist, ist es sehr selten, dass diese Suchvorgänge ausgeführt werden sind eigentlich ein Engpass in Ihrer Anwendung. Wenn Sie es als eins messen können, können Sie versuchen, es zu optimieren - aber sonst verschwenden Sie Ihre Zeit.
Eloff
15
Was ist, wenn Sie eine kleine Sammlung haben, die viele Male in einer Schleife getroffen wird? Das ist kein ungewöhnliches Szenario.
Dan-Gph
3
@ om-nom-nom - Ich denke, der Punkt ist, dass es keine Rolle spielt, wo der Wendepunkt liegt, denn: "Wenn die Leistung ein Problem darstellt, verwenden Sie HashSet<T>. In Fällen mit geringer Anzahl, in denen die List<T>Geschwindigkeit möglicherweise höher ist, ist der Unterschied unbedeutend . "
Scott Smith
66

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 es HashSet<T>immer noch eine schlechte Wahl, List<T>da es relativ weniger fehlertolerant ist.

Trotzdem werde ich einige andere Aspekte der Leistung untersuchen.

+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |
|            | access |             |           |          |          |           |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T>    | O(1)   | O(n)        | O(n)      | O(1)*    | O(n)     | Lesser    |
| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)     | O(1)     | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+
  • 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.

nawfal
quelle
11
Meine Frage (vor sechs Jahren) betraf nicht die theoretische Leistung.
Michael Damatov
1
HashSet erlaubt zufälligen Zugriff mit ElementAt (), und ich denke, das wäre O (n) Zeit. Vielleicht könnten Sie auch in Ihre Tabelle einfügen, ob jede Sammlung Duplikate zulässt (z. B. Listen, aber Hashsets nicht).
Dan W
1
@DanW in der Tabelle Ich vergleiche reine Leistung, nicht Verhaltensmerkmale. Danke für den ElementAt-Tipp.
Nawfal
1
ElementAt ist nur eine LINQ-Erweiterung. Es macht nichts, was Sie nicht können, und optimiert es besser in einer anderen Methode, die Sie selbst hinzufügen. Ich denke, die Tabelle war sinnvoller, ohne ElementAt zu berücksichtigen, da alle anderen Methoden für diese Klassen explizit vorhanden sind.
Dinerdo
Vielen Dank für diese Tabelle. In meinem Anwendungsfall muss ich jedes Mal, wenn sie aktiviert / deaktiviert sind, Ziele zu einer aufgefüllten Sammlung hinzufügen und daraus entfernen. Dies hat mir geholfen, die richtige Wahl zu treffen (HashSet).
Casey Hofland
50

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)).

Ader
quelle
Die Liste berechnet möglicherweise den Versatz für das bestimmte Element anhand seines Index (da alle Elemente vom gleichen Typ sind und möglicherweise dieselbe Speichergröße belegen). Also Liste ist nicht notwendig, zählt seine Elemente auf
Lu55
@ Lu55 - Bei der Frage geht es um die Suche nach einem Artikel in einer Sammlung. Ein typisches Szenario ist, dass die Sammlung dynamisch ist - Elemente wurden möglicherweise hinzugefügt oder gelöscht, seit Sie das letzte Mal nach einem bestimmten Element gesucht haben -, sodass ein Index nicht aussagekräftig ist (da er sich geändert hat). Wenn Sie über eine statische Sammlung verfügen (die sich während der Berechnung nicht ändert) oder Elemente nie gelöscht und immer am Ende hinzugefügt werden, Listwird a bevorzugt, da Sie sich an einen Index erinnern können - das ist die Situation, in der Sie sich befinden beschreiben.
ToolmakerSteve
Sie können ein SortedSet verwenden, wenn Sie ein HashSet sortieren müssen. Immer noch viel schneller als eine Liste.
Live-Love
25

Ich dachte nur, ich würde einige Benchmarks für verschiedene Szenarien verwenden, um die vorherigen Antworten zu veranschaulichen:

  1. Einige (12 - 20) kleine Zeichenfolgen (Länge zwischen 5 und 10 Zeichen)
  2. Viele (~ 10K) kleine Saiten
  3. Einige lange Zeichenfolgen (Länge zwischen 200 und 1000 Zeichen)
  4. Viele (~ 5K) lange Saiten
  5. Ein paar ganze Zahlen
  6. Viele (~ 10K) Ganzzahlen

Und für jedes Szenario nach Werten suchen, die angezeigt werden:

  1. Am Anfang der Liste ("Start", Index 0)
  2. Am Anfang der Liste ("früh", Index 1)
  3. In der Mitte der Liste ("Mitte", Indexanzahl / 2)
  4. Gegen Ende der Liste ("spät", Indexanzahl 2)
  5. Am Ende der Liste ("Ende", Indexanzahl 1)

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)

stopwatch.start
for X times
    exists = list.Contains(lookup);
stopwatch.stop

stopwatch.start
for X times
    exists = hashset.Contains(lookup);
stopwatch.stop

Beispielausgabe

Getestet unter Windows 7, 12 GB RAM, 64 Bit, Xeon 2,8 GHz

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...

Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]


---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...

Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]


---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]


---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]


---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...

Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]


---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]
drzaus
quelle
7
Interessant. Vielen Dank, dass Sie dies ausgeführt haben. Leider vermute ich, dass diese Diskussionen unnötige Umgestaltungen auslösen. Hoffentlich ist für die meisten Menschen der Vorteil, dass in Ihrem absoluten Worst-Case-Szenario Listimmer noch nur 0,17 Millisekunden für die Durchführung einer einzelnen Suche benötigt werden und wahrscheinlich keine Substitution erforderlich ist, HashSetbis die Suchfrequenz absurde Werte erreicht. Bis dahin ist die Verwendung von List normalerweise das geringste Problem.
Paul Walls
Dies sind vorerst keine aktuellen Informationen. Oder vielleicht ist es ursprünglich falsch. Ich habe nur kleine Werte von 2 bis 8 Zeichen überprüft. List / HashSet wurden für jeweils 10 Werte erstellt ... HashSet für 30% langsamer ... Wenn die Kapazität in List verwendet wird, beträgt die Differenz sogar ~ 40%. HashSet wird nur dann um 10% schneller, wenn die Liste ohne angegebene Kapazität ist und jeden Wert überprüft, bevor die gesamte Liste hinzugefügt wird.
Maxim
Wenn die Anzahl der Gegenstände auf 4 reduziert wird, gewinnt List auch im schlimmsten Fall erneut (mit 10% Unterschied). Daher empfehle ich nicht, HashSet für eine kleine Sammlung von Zeichenfolgen zu verwenden (sagen wir <20). Und es unterscheidet sich von Ihren "wenigen kleinen" Tests.
Maxim
1
@Maxim kann nicht wirklich sagen, dass meine Ergebnisse "falsch" sind - genau das ist auf meinem Computer passiert. YMMV. Tatsächlich habe ich sie gerade erneut ausgeführt ( gist.github.com/zaus/014ac9b5a78b267aa1643d63d30c7554 ) auf einem neuen Win10 4.0GHz 16 GB Solid State Computer und ähnliche Ergebnisse erzielt. Ich sehe, dass die Hashset-Leistung konsistenter war, unabhängig davon, wo sich der Suchschlüssel befand oder wie groß die Liste war, während die Listenleistung stark von besser bis mehr als 300x langsamer variierte. Aber wie PaulWalls anfangs kommentierte, sprechen wir von einer ernsthaften # Mikrooptimierung.
Drzaus
@ Maxim als Referenz: dotnetfiddle.net/5taRDd - zögern Sie nicht, damit herumzuspielen .
Drzaus
10

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.

Walden Leverich
quelle
1
Sie müssen auch die Kosten für einen Vergleich berücksichtigen. Im Fall von Contains (T) führt das HashSet einen Vergleich durch, um zu überprüfen, ob es keine Hash-Kollision mit der Liste gibt, die einen Vergleich für jedes betrachtete Element durchführt, bevor es das richtige findet. Sie müssen auch die Verteilung der von T.GetHashCode () generierten Hashes berücksichtigen, als ob dies immer den gleichen Wert zurückgibt, den Sie HashSet grundsätzlich dazu bringen, dasselbe wie List zu tun.
Martin Brown
6

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

  1. Ein Datensatz
  2. Nutzungsanforderungen

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.

Robert P.
quelle
5

Sie können ein HybridDictionary verwenden, das die Bruchstelle automatisch erkennt und Nullwerte akzeptiert, sodass es im Wesentlichen mit einem HashSet identisch ist.

Muis
quelle
1
Ich habe dies für die Idee positiv bewertet, aber niemand, bitte nutzen Sie dies heute. Sag nein zu Nicht-Generika. Auch ein Wörterbuch ist eine Schlüsselwertzuordnung, die nicht gesetzt ist.
Nawfal
4

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.

Adam Rosenfield
quelle
3

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?

Peter
quelle
3

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.

JaredPar
quelle
0

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!

Kyle
quelle
1
JVM ... oder CLR :-)
bvgheluwe