Ich wollte einige Pixelpositionen speichern, ohne Duplikate zuzulassen, daher fallen mir als Erstes HashSet<Point>
ähnliche Klassen ein. Dies scheint jedoch im Vergleich zu so etwas sehr langsam zu sein HashSet<string>
.
Zum Beispiel dieser Code:
HashSet<Point> points = new HashSet<Point>();
using (Bitmap img = new Bitmap(1000, 1000))
{
for (int x = 0; x < img.Width; x++)
{
for (int y = 0; y < img.Height; y++)
{
points.Add(new Point(x, y));
}
}
}
dauert etwa 22,5 Sekunden.
Der folgende Code (der aus offensichtlichen Gründen keine gute Wahl ist) dauert nur 1,6 Sekunden:
HashSet<string> points = new HashSet<string>();
using (Bitmap img = new Bitmap(1000, 1000))
{
for (int x = 0; x < img.Width; x++)
{
for (int y = 0; y < img.Height; y++)
{
points.Add(x + "," + y);
}
}
}
Meine Fragen sind also:
- Gibt es einen Grund dafür? Ich habe diese Antwort überprüft , aber 22,5 Sekunden sind weit mehr als die in dieser Antwort angegebenen Zahlen.
- Gibt es eine bessere Möglichkeit, Punkte ohne Duplikate zu speichern?
c#
.net
performance
collections
hashset
Ahmed Abdelhameed
quelle
quelle
Antworten:
Es gibt zwei Perf-Probleme, die durch die Punktstruktur hervorgerufen werden. Etwas, das Sie sehen können, wenn Sie dem Testcode hinzufügen
Console.WriteLine(GC.CollectionCount(0));
. Sie werden sehen, dass für den Punkttest ~ 3720 Sammlungen erforderlich sind, für den Stringtest jedoch nur ~ 18 Sammlungen. Nicht gratis. Wenn Sie sehen, dass ein Werttyp so viele Sammlungen hervorruft, müssen Sie zu dem Schluss kommen, dass es zu viel Boxen gibt.Am Problem ist , dass
HashSet<T>
ein mussIEqualityComparer<T>
seine Arbeit zu erledigen. Da Sie keine angegeben haben, muss auf eine zurückgegeben werden, die von zurückgegeben wurdeEqualityComparer.Default<T>()
. Diese Methode kann einen guten Job für Zeichenfolgen machen, sie implementiert IEquatable. Aber nicht für Point, es ist ein Typ, der aus .NET 1.0 stammt und nie die Liebe der Generika bekommen hat. Es kann lediglich die Object-Methoden verwenden.Das andere Problem ist, dass Point.GetHashCode () in diesem Test keine hervorragende Arbeit leistet, zu viele Kollisionen, so dass Object.Equals () ziemlich stark hämmert. String hat eine ausgezeichnete GetHashCode-Implementierung.
Sie können beide Probleme lösen, indem Sie dem HashSet einen guten Vergleicher zur Verfügung stellen. Wie dieser:
Und benutze es:
Und jetzt ist es ungefähr 150-mal schneller und kann den Saitentest problemlos bestehen.
quelle
obj.X << 16 | obj.Y;
Implementierung gekommen ?|
. Für 3 Zahlen könnte es sinnvoll sein, 22 und 11 als Verschiebung zu verwenden. Für 4 Zahlen wäre es 24, 16, 8. Es wird jedoch immer noch Kollisionen geben, aber nur, wenn die Zahlen groß werden. Entscheidend ist aber auch dieHashSet
Umsetzung. Wenn Open-Adressing mit "Bit-Kürzung" verwendet wird (ich glaube nicht!), Ist der Ansatz der Linksverschiebung möglicherweise schlecht.Der Hauptgrund für den Leistungsabfall ist das ganze Boxen (wie bereits in der Antwort von Hans Passant erklärt ).
Abgesehen davon verschlimmert der Hash-Code-Algorithmus das Problem, da er mehr Aufrufe verursacht,
Equals(object obj)
wodurch die Anzahl der Box-Conversions erhöht wird.Beachten Sie auch, dass der Hash-Code von von
Point
berechnet wirdx ^ y
. Dies führt zu einer sehr geringen Streuung in Ihrem Datenbereich, und daher sind die Buckets derHashSet
überfüllt - etwas, das nicht passiertstring
, wenn die Streuung der Hashes viel größer ist.Sie können dieses Problem lösen, indem Sie Ihre eigene
Point
Struktur implementieren (trivial) und einen besseren Hash-Algorithmus für Ihren erwarteten Datenbereich verwenden, z. B. indem Sie die Koordinaten verschieben:Lesen Sie den Blog-Beitrag von Eric Lippert zu diesem Thema , um gute Ratschläge zu Hash-Codes zu erhalten .
quelle
GetHashCode
tritt das auf:unchecked(x ^ y)
währendstring
es viel komplizierter aussieht.HashSet<long>()
stattdessen versucht, stattdessen zu verwenden undlist.Add(unchecked(x ^ y));
dem HashSet Werte hinzuzufügen. Dies war sogar noch schneller alsHashSet<string>
(345 ms) . Unterscheidet sich das irgendwie von dem, was Sie beschrieben haben?list
wenn Sie mit dem Auffüllen fertig sind?point
derHashSet
intern aufGetHashCode
und ruft für jeden dieser Punkte mit demselben Hashcode an,Equals
um festzustellen, ob er bereits vorhanden istPoint
wenn Sie eine Klasse erstellen können, dieIEqualityComparer<Point>
andere Dinge implementiert und mit ihnen kompatibel ist, mit denen Sie arbeiten,Point
während Sie den Vorteil haben, dass Sie nicht die Armen habenGetHashCode
und sich einschließen müssenEquals()
.