Dlaczego HashSet jest tak dużo wolniejszy niż HashSet?

Question

Dlaczego HashSet jest tak dużo wolniejszy niż HashSet?

Chciałem przechowywać niektóre lokalizacje pikseli bez zezwalania na duplikaty, więc pierwsze co przychodzi mi na myśl to {[2] } lub podobne klasy. Jednak wydaje się to być bardzo powolne w porównaniu do czegoś takiego jak 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 następujący kod (co nie jest dobrym wyborem z oczywistych powodów) 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);
        }
    }
}

Moje pytania to:

Czy Jest jakiś powód za to? Sprawdziłem Ta odpowiedź, ale 22,5 sek to znacznie więcej niż liczby pokazane w tej odpowiedzi.
czy jest lepszy sposób na przechowywanie punktów bez duplikatów?

157

performance collections .net c#hashset

Author: Ahmed Abdelhameed, 2017-09-10

Source

2 answers

Głównym powodem spadku wydajności jest cały boks (jak już wyjaśniono w Hans Passant ' s odpowiedź).

Poza tym algorytm hash code pogarsza problem, ponieważ powoduje więcej wywołań do Equals(object obj), zwiększając tym samym ilość konwersji boksu.

Zauważ również, że kod hashowyPoint jest obliczana przez x ^ y. Powoduje to bardzo małe rozproszenie w zakresie danych, a zatem wiadra HashSet są przeludnione - coś, co nie dzieje się z string, gdzie rozproszenie hashów jest znacznie większe.

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

(x << 16) ^ y

Aby uzyskać dobre rady, jeśli chodzi o kody hashowe, przeczytaj Eric Lippert na blogu na ten temat .

86

Author: InBetween,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-09-16 22:22:42

score 276 · Accepted Answer

Istnieją dwa problemy perf wywołane strukturą punktową. Coś, co możesz zobaczyć po dodaniu Console.WriteLine(GC.CollectionCount(0)); do kodu testowego. Zobaczysz, że test punktowy wymaga kolekcji ~3720, ale test ciągów wymaga tylko ~ 18 kolekcji. Nie za darmo. Gdy widzisz typ wartości wywołujący tak wiele kolekcji, musisz stwierdzić "uh-oh, too much boxing".

Problem polega na tym, że HashSet<T> potrzebuje IEqualityComparer<T>, Aby wykonać swoją pracę. Ponieważ nie dostarczyłeś jednego, musi wrócić do jednego zwróconego przez EqualityComparer.Default<T>(). Ta metoda może zrobić dobrą robotę dla string, implementuje IEquatable. Ale nie chodzi o to, że jest to typ, który czerpie z. NET 1.0 i nigdy nie dostał miłości generycznej. Wszystko, co może zrobić, to użyć metod obiektu.

Inną kwestią jest ten punkt.GetHashCode() nie wykonuje w tym teście zbyt wielu kolizji, więc uderza w obiekt.Equals() String ma doskonałą implementację GetHashCode.

Możesz rozwiązać oba problemy, dostarczając HashSet z dobre porównanie. 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());

I jest teraz około 150 razy szybszy, łatwo pokonując test strun.