HashSet vs. Liste Leistung
https://stackoverflow.com/questions/150750
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Es ist klar, dass eine Suchleistung der generischen HashSet<T> Klasse höher als der allgemeinen List<T> Klasse. Man vergleiche nur die Hash-basierten Schlüssel mit dem linearen Ansatz in der List<T> Klasse.
Allerdings Berechnung eines Hash-Schlüssel kann selbst einige CPU-Zyklen dauern, so dass für eine kleine Menge von Elementen der linearen Suche eine echte Alternative zum HashSet<T> sein kann.
Meine Frage: wo ist die Break-even
, um das Szenario zu vereinfachen (und fair zu sein) nehmen wir an, dass die List<T>-Klasse verwendet, die Equals() Methode des Elements ein Element zu identifizieren.
Lösung
Eine Menge Leute sagen, dass, wenn Sie auf die Größe, wo Geschwindigkeit tatsächlich ein Anliegen ist, die immer HashSet<T> schlagen List<T>, aber das hängt davon ab, was Sie tun.
Angenommen, Sie haben einen List<T> haben, die immer nur im Durchschnitt 5 Elemente darin haben wird. Über eine große Anzahl von Zyklen, wenn ein einzelnes Element hinzugefügt wird oder in jedem Zyklus entfernt, können Sie auch besser dran, einen List<T> verwenden.
Ich habe einen Test für diese auf meinem Rechner, und, na ja, es ist sehr sehr klein zu sein hat einen Vorteil von List<T> zu bekommen. Eine Liste der kurzen Strings, ging der Vorteil weg nach Größe 5, für Objekte 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 ist, dass die Daten als Grafik angezeigt:
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();
}
Andere Tipps
Sie befinden sich in diesem falsch. Ja eine lineare Suche nach einer Liste wird ein HashSet für eine kleine Anzahl von Elementen spielt. Aber der Unterschied in der Leistung keine Rolle in der Regel nicht für Sammlungen so klein. Es ist in der Regel die großen Sammlungen Sie haben Grund zur Sorge, und das ist, wo man a href <= "http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right- sammel class.aspx“rel = "noreferrer"> denken in der Big-O . Wenn Sie jedoch einen echten Engpass auf HashSet Leistung gemessen haben, dann können Sie versuchen, eine Hybrid-List / HashSet zu erstellen, aber Sie werden das tun durch viele empirische Leistungstests der Durchführung -. Keine Fragen auf SO fragen
Es ist im Wesentlichen sinnlos zwei Strukturen vergleichen Leistung , die sich anders verhalten. Verwenden, um die Struktur, die die Absicht vermittelt. Auch wenn Sie Ihre List<T> sagen keine Duplikate haben würde und Iteration Reihenfolge keine Rolle spielt es vergleichbar mit einem HashSet<T> machen, die immer noch eine schlechte Wahl zu verwenden List<T> weil seine relativ weniger fehlertolerant.
Das heißt, ich werde prüfen einige andere Aspekte Leistung,
+------------+--------+-------------+-----------+----------+----------+-----------+
| 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** |
+------------+--------+-------------+-----------+----------+----------+-----------+
* Even though addition is O(1) in both cases, it will be relatively slower in HashSet<T> since it involves cost of precomputing hash code before storing it.
Ob ein HashSet verwenden <> oder List <> kommt auf , wie Sie benötigen, um Ihre Sammlung zugreifen . Wenn Sie die Reihenfolge der Elemente gewährleisten müssen, verwenden Sie eine Liste. Wenn Sie nicht tun, verwenden Sie einen HashSet. Lassen Sie Microsoft Sorgen über die Umsetzung ihrer Hash-Algorithmen und Objekte.
Ein HashSet wird Elemente zugreifen, ohne die Sammlung (Komplexität der O (1) aufzuzählen oder in der Nähe davon), und weil eine List, um garantiert, im Gegensatz zu einem HashSet, werden einige Elemente müssen aufgezählt werden (Komplexität von O (n)).
dachte nur, dass ich mit einigem Benchmarks für verschiedene Szenarien läuten würde die bisherigen Antworten zu veranschaulichen:
- Ein paar (12-20) kleine Strings (Länge zwischen 5 und 10 Zeichen)
- Viele (~ 10K) kleine Strings
- Ein paar langen Strings (Länge zwischen 200 und 1000 Zeichen)
- Viele (~ 5K) lange Zeichenketten
- Einige Zahlen
- Viele (~ 10K) ganze Zahlen
Für jedes Szenario aufzublicken Werte, die angezeigt werden:
- Am Anfang der Liste ( "Start", Index 0)
- In der Nähe des Anfang der Liste ( "early", Index 1)
- In der Mitte der Liste ( "mittleren", Indexzählwert / 2)
- In der Nähe des Endes der Liste ( "spät", Indexzählwert-2)
- Am Ende der Liste ( "Ende", Index count-1)
Vor jedem Szenario, das ich zufällig generierte Größe Listen von zufälligen Zeichenfolge, und dann jede Liste in eine Hashset zugeführt. Jedes Szenario lief 10.000-mal, im Wesentlichen:
(Test Pseudo-Code)
stopwatch.start
for X times
exists = list.Contains(lookup);
stopwatch.stop
stopwatch.start
for X times
exists = hashset.Contains(lookup);
stopwatch.stop
Beispielausgabe
Getestet auf Windows 7, 12GB 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]
Der Break-even wird über die Kosten hängen den Hash der Berechnung. Hash-Berechnungen können trivial sein, oder nicht ... :-) Es gibt immer die System.Collections.Specialized.HybridDictionary Klasse zu helfen, man muss nicht über die Break-even kümmern.
Die Antwort, wie immer, ist " Es hängt ". Ich gehe davon aus den Tags Sie sprechen C #.
Ihre beste Wette ist, um zu bestimmen
- Eine Reihe von Daten
- Gebrauchsbedingungen
und einige Testfälle schreiben.
Es hängt auch davon ab, wie Sie die Liste sortieren (wenn es überhaupt sortiert ist), was für eine Art von Vergleichen durchgeführt werden muß, wie lange die „Vergleichen“ -Operation für das jeweilige Objekt in der Liste nimmt, oder sogar, wie Sie beabsichtigen, die Sammlung zu verwenden.
Im Allgemeinen ist die beste zu wählen ist nicht so sehr auf der Grundlage der Größe der Daten, mit dem Sie arbeiten, sondern vielmehr, wie Sie beabsichtigen, darauf zuzugreifen. Haben Sie jedes Stück von Daten mit einer bestimmten Zeichenfolge verbunden ist, oder andere Daten? Eine Hash-basierte Sammlung wäre wahrscheinlich am besten. Ist die Reihenfolge der Daten, die Sie speichern wichtig, oder werden Sie alle Daten gleichzeitig zugreifen müssen? Eine regelmäßige Liste kann dann besser sein.
Zusätzlich:
Natürlich meine obigen Ausführungen annehmen ‚Leistung‘ bedeutet Datenzugriff. Etwas anderes zu berücksichtigen: was Sie suchen, wenn Sie sagen, „Leistung“? Ist die Leistung einzelner Wert nachschlagen? Ist es Management von großen (10000, 100000 oder mehr) Wert setzt? Ist es die Performance der Datenstruktur mit Daten füllen? Entfernen von Daten? Zugriff auf einzelne Bits von Daten? Ersetzen Werte? Iterieren über die Werte? Speichernutzung? Datenkopiergeschwindigkeit? Wenn Sie beispielsweise Daten zugreifen, indem Sie einen String-Wert, aber Ihr wichtigster Leistungsbedarf ist minimal Speichernutzung, könnten Sie widerstreitende Design-Probleme haben.
Sie können einen Hybriddictionary benutzen, die automatisch die Bruchstelle erkennt und akzeptiert Null-Werte, es im Wesentlichen das gleiche wie ein HashSet machen.
Es hängt davon ab. Wenn die genaue Antwort wirklich wichtig ist, einige der Profilierung und finden Sie heraus. Wenn Sie sicher sind, nie mehr haben Sie als eine bestimmte Anzahl von Elementen in dem Satz, mit einer Liste gehen. Wenn die Anzahl unbegrenzt ist, eine HashSet verwenden.
Abhängig von, was Sie Hashing. Wenn Sie Ihre Schlüssel ganze Zahlen sind brauchen Sie wahrscheinlich nicht sehr viele Einzelteile, bevor die HashSet schneller ist. Wenn Sie es auf einer Schnur sind Keying dann wird es langsamer und hängt von der Eingabezeichenfolge.
Sicher könnte man einen Maßstab ziemlich leicht Peitsche?
Ein Faktor Sie nicht berücksichtigt ist die Robustheit der GetHashCode () Funktion. Mit einer perfekten Hash-Funktion haben die HashSet deutlich besser wird die Leistung zu suchen. Aber als die Hash-Funktion verringert werden, so dass die HashSet Suchzeit.
Abhängig von vielen Faktoren ab ... Liste Implementierung, CPU-Architektur, JVM, Loop-Semantik, die Komplexität der Methode equals, etc ... Mit der Zeit wird die Liste groß genug, um effektiv Benchmark (1000 Elemente), Hash -basierte binäre Lookups schlagen lineare Suche hands-down, und die Differenz skaliert nur von dort oben.
Hope, das hilft!
