Warum ist HashSet <Point> so viel langsamer als HashSet <string>?

165

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?
Ahmed Abdelhameed
quelle
Was sind diese "offensichtlichen Gründe" dafür, keine verketteten Zeichenfolgen zu verwenden? Was ist der bessere Weg, wenn ich meinen eigenen IEqualityComparer nicht implementieren möchte?
Ivan Yurchenko

Antworten:

290

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 muss IEqualityComparer<T>seine Arbeit zu erledigen. Da Sie keine angegeben haben, muss auf eine zurückgegeben werden, die von zurückgegeben wurde EqualityComparer.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:

class PointComparer : IEqualityComparer<Point> {
    public bool Equals(Point x, Point y) {
        return x.X == y.X && x.Y == y.Y;
    }

    public int GetHashCode(Point obj) {
        // Perfect hash for practical bitmaps, their width/height is never >= 65536
        return (obj.Y << 16) ^ obj.X;
    }
}

Und benutze es:

HashSet<Point> list = new HashSet<Point>(new PointComparer());

Und jetzt ist es ungefähr 150-mal schneller und kann den Saitentest problemlos bestehen.

Hans Passant
quelle
26
+1 für die Implementierung der GetHashCode-Methode. Wie sind Sie aus Neugier zu einer bestimmten obj.X << 16 | obj.Y;Implementierung gekommen ?
Akash KC
32
Es wurde von der Art und Weise inspiriert, wie die Maus ihre Position in Fenstern übergibt. Es ist ein perfekter Hash für jede Bitmap, die Sie jemals anzeigen möchten.
Hans Passant
2
Gut das zu wissen. Gibt es eine Dokumentation oder die beste Richtlinie zum Schreiben von Hashcode wie Ihres? Eigentlich würde ich immer noch gerne wissen, ob der obige Hashcode mit Ihrer Erfahrung oder einer Richtlinie, die Sie befolgen, einhergeht.
Akash KC
5
@AkashKC Ich bin nicht sehr erfahren mit C #, aber soweit ich weiß, sind ganze Zahlen im Allgemeinen 32 Bit. In diesem Fall möchten Sie den Hash von 2 Zahlen und indem Sie ein 16-Bit nach links verschieben, stellen Sie sicher, dass die "unteren" 16-Bit jeder Zahl das andere nicht "beeinflussen" |. 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 die HashSetUmsetzung. Wenn Open-Adressing mit "Bit-Kürzung" verwendet wird (ich glaube nicht!), Ist der Ansatz der Linksverschiebung möglicherweise schlecht.
MSeifert
3
@HansPassant: Ich frage mich, ob die Verwendung von XOR anstelle von OR in GetHashCode möglicherweise etwas besser ist - für den Fall, dass die Punktkoordinaten 16 Bit überschreiten (möglicherweise nicht auf gängigen Anzeigen, aber in naher Zukunft). // XOR ist in Hash-Funktionen normalerweise besser als OR, da es weniger Informationen verliert, reversibke ist usw. // zB Wenn negative Koordinaten zulässig sind, überlegen Sie, was mit dem X-Beitrag passiert, wenn Y negativ ist.
Krazy Glew
85

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 vonPoint berechnet wird x ^ y. Dies führt zu einer sehr geringen Streuung in Ihrem Datenbereich, und daher sind die Buckets der HashSetüberfüllt - etwas, das nicht passiert string, wenn die Streuung der Hashes viel größer ist.

Sie können dieses Problem lösen, indem Sie Ihre eigene PointStruktur implementieren (trivial) und einen besseren Hash-Algorithmus für Ihren erwarteten Datenbereich verwenden, z. B. indem Sie die Koordinaten verschieben:

(x << 16) ^ y

Lesen Sie den Blog-Beitrag von Eric Lippert zu diesem Thema , um gute Ratschläge zu Hash-Codes zu erhalten .

Zwischen
quelle
4
Wenn man sich die Referenzquelle von Point ansieht, GetHashCodetritt das auf: unchecked(x ^ y)während stringes viel komplizierter aussieht.
Gilad Green
2
Hmm .. Nun, um zu überprüfen, ob Ihre Annahme richtig ist, habe ich HashSet<long>()stattdessen versucht, stattdessen zu verwenden und list.Add(unchecked(x ^ y));dem HashSet Werte hinzuzufügen. Dies war sogar noch schneller als HashSet<string> (345 ms) . Unterscheidet sich das irgendwie von dem, was Sie beschrieben haben?
Ahmed Abdelhameed
4
@AhmedAbdelhameed Das liegt wahrscheinlich daran, dass Sie Ihrem Hash-Set viel weniger Mitglieder hinzufügen, als Sie denken (wiederum aufgrund der schrecklichen Streuung des Hash-Code-Algorithmus). Was zählt, listwenn Sie mit dem Auffüllen fertig sind?
Zwischen dem
4
@AhmedAbdelhameed Dein Test ist falsch. Sie fügen immer wieder dieselben Longs hinzu, sodass Sie nur wenige Elemente einfügen. Beim Einfügen ruft pointder HashSetintern auf GetHashCodeund ruft für jeden dieser Punkte mit demselben Hashcode an, Equalsum festzustellen, ob er bereits vorhanden ist
Ofir Winegarten
49
Sie müssen nicht implementieren, Pointwenn Sie eine Klasse erstellen können, die IEqualityComparer<Point>andere Dinge implementiert und mit ihnen kompatibel ist, mit denen Sie arbeiten, Pointwährend Sie den Vorteil haben, dass Sie nicht die Armen haben GetHashCodeund sich einschließen müssen Equals().
Jon Hanna