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

165

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?
Ahmed Abdelhameed
źródło
Jakie są te „oczywiste powody” nieużywania połączonych ciągów? Jaki jest lepszy sposób na zrobienie tego, jeśli nie chcę implementować własnego IEqualityComparer?
Ivan Yurchenko

Odpowiedzi:

290

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.

Hans Passant
źródło
26
+1 za zapewnienie implementacji metody GetHashCode. Z ciekawości, skąd wzięłaś się z konkretną obj.X << 16 | obj.Y;implementacją.
Akash KC
32
Został zainspirowany sposobem, w jaki mysz przechodzi swoją pozycję w oknach. Jest to doskonały skrót do każdej mapy bitowej, którą chciałbyś kiedykolwiek wyświetlić.
Hans Passant,
2
Dobrze wiedzieć. Jakaś dokumentacja lub najlepsze wytyczne dotyczące pisania hashcode, takiego jak twój? Właściwie nadal chciałbym wiedzieć, czy powyższy kod jest związany z twoim doświadczeniem, czy z jakąkolwiek wskazówką, której się trzymasz.
Akash KC
5
@AkashKC Nie mam dużego doświadczenia z C #, ale z tego co wiem, liczby całkowite to na ogół 32 bity. W tym przypadku chcesz mieszać 2 liczby i przesuwając w lewo jedną o 16 bitów, upewniasz się, że „niższe” 16 bitów każdej liczby nie „wpływa” na drugą |. Dla 3 liczb sensowne może być użycie 22 i 11 jako przesunięcia. Dla 4 liczb byłoby to 24, 16, 8. Jednak nadal będą występować kolizje, ale tylko wtedy, gdy liczby będą duże. Ale zależy to również przede wszystkim od HashSetimplementacji. Jeśli używa otwartego adresowania z "bitowym obcięciem" (nie sądzę!), Podejście z przesunięciem w lewo może być złe.
MSeifert
3
@HansPassant: Zastanawiam się, czy użycie XOR zamiast OR w GetHashCode może być nieco lepsze - w przypadku, gdy współrzędne punktu mogą przekraczać 16 bitów (być może nie na zwykłych wyświetlaczach, ale w niedalekiej przyszłości). // XOR jest zwykle lepszy w funkcjach skrótu niż OR, ponieważ traci mniej informacji, jest odwrócony itp. // np. Jeśli dozwolone są ujemne współrzędne, zastanów się, co się stanie z wkładem X, jeśli Y jest ujemne.
Krazy Glew
85

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 .

Pomiędzy
źródło
4
Patrząc na referencyjne źródło Pointa, GetHashCodedziała: unchecked(x ^ y)podczas stringgdy wygląda to na znacznie bardziej skomplikowane ..
Gilad Green
2
Hmm ... cóż, aby sprawdzić, czy twoje założenie jest poprawne, po prostu próbowałem użyć HashSet<long>()zamiast tego i list.Add(unchecked(x ^ y));dodałem wartości do HashSet. To było nawet szybsze niż HashSet<string> (345 ms) . Czy różni się to w jakiś sposób od tego, co opisałeś?
Ahmed Abdelhameed
4
@AhmedAbdelhameed to prawdopodobnie dlatego, że dodajesz znacznie mniej członków do swojego zestawu skrótów, niż zdajesz sobie sprawę (ponownie z powodu okropnego rozproszenia algorytmu kodu skrótu). Jaka jest liczba, listkiedy skończysz go wypełniać?
Pomiędzy
4
@AhmedAbdelhameed Twój test jest zły. W kółko dodajesz te same długie fragmenty, więc w rzeczywistości jest tylko kilka elementów, które wstawiasz. Wkładając pointThe HashSetbędą wewnętrznie zadzwonić GetHashCodei dla każdego z tych punktów o tej samej hashcode, zadzwoni Equalsaby ustalić, czy jest on już istnieje
Ofir Winegarten
49
Nie ma potrzeby implementacji, Pointgdy można stworzyć klasę, która implementuje IEqualityComparer<Point>i zachowuje zgodność z innymi rzeczami, z którymi współpracuje, Pointjednocześnie czerpiąc korzyści z braku ubogich GetHashCodei konieczności dołączania Equals().
Jon Hanna,