Dlaczego HashSet <Point> jest o wiele wolniejszy niż HashSet <string>?

Chciałem przechowywać niektóre lokalizacje pikseli bez zezwalania na duplikaty, więc pierwsze co przychodzi mi na myśl to HashSet<Point>lub podobne klasy. Jednak wydaje się to być bardzo powolne w porównaniu do czegoś podobnego HashSet<string>.

Na przykład ten kod:

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));
        }
    }
}

trwa około 22,5 sekundy.

Podczas gdy poniższy kod (który z oczywistych powodów nie jest dobrym wyborem) zajmuje tylko 1,6 sekundy:

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);
        }
    }
}

Tak więc moje pytania to:

• Czy jest powód ku temu? Sprawdziłem tę odpowiedź , ale 22,5 sekundy to znacznie więcej niż liczby pokazane w tej odpowiedzi.
• Czy jest lepszy sposób na przechowywanie punktów bez duplikatów?

Struct Point wywołuje dwa problemy z perfekcją. Coś, co możesz zobaczyć, dodając Console.WriteLine(GC.CollectionCount(0));do kodu testowego. Zobaczysz, że test Point wymaga ~ 3720 kolekcji, ale test ciągów wymaga tylko ~ 18 kolekcji. Nie za darmo. Kiedy widzisz, że typ wartości wywołuje tak wiele kolekcji, to musisz wywnioskować „uh-oh, za dużo boksu”.

Chodzi o to, że HashSet<T>musi on IEqualityComparer<T>wykonać swoją pracę. Ponieważ go nie dostarczyłeś, musi wrócić do tego, który został zwrócony przez EqualityComparer.Default<T>(). Ta metoda może zrobić dobrą robotę dla stringów, implementuje IEquatable. Ale nie dla Point, jest to typ, który nawiązuje do .NET 1.0 i nigdy nie spodobał się rodzajom. Wszystko, co może zrobić, to użyć metod Object.

Innym problemem jest to, że Point.GetHashCode () nie wykonuje świetnej pracy w tym teście, zbyt wiele kolizji, więc dość mocno wbija Object.Equals (). String ma doskonałą implementację GetHashCode.

Możesz rozwiązać oba problemy, dostarczając HashSet z dobrym narzędziem porównującym. Jak ten:

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;
    }
}

I użyj go:

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

Jest teraz około 150 razy szybszy, z łatwością pokonując test strun.

Głównym powodem spadku wydajności jest cały boks (jak już wyjaśniono w odpowiedzi Hansa Passanta ).

Poza tym algorytm kodu skrótu pogarsza problem, ponieważ powoduje więcej wywołań, Equals(object obj)zwiększając tym samym ilość konwersji bokserskich.

Należy również zauważyć, że kod skrótu programuPoint jest obliczany przez x ^ y. Daje to bardzo małe rozproszenie w zakresie danych, a zatem przedziały HashSetsą przepełnione - coś, co się nie dzieje string, gdy rozproszenie skrótów jest znacznie większe.

Możesz rozwiązać ten problem, implementując własną Pointstrukturę (trywialną) i używając lepszego algorytmu mieszającego dla oczekiwanego zakresu danych, np. Przesuwając współrzędne:

(x << 16) ^ y

Aby uzyskać dobre rady dotyczące kodów skrótów, przeczytaj wpis na blogu Erica Lipperta na ten temat .