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?
c#
.net
performance
collections
hashset
Ahmed Abdelhameed
źródło
źródło
Odpowiedzi:
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 onIEqualityComparer<T>
wykonać swoją pracę. Ponieważ go nie dostarczyłeś, musi wrócić do tego, który został zwrócony przezEqualityComparer.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:
I użyj go:
Jest teraz około 150 razy szybszy, z łatwością pokonując test strun.
źródło
obj.X << 16 | obj.Y;
implementacją.|
. 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 odHashSet
implementacji. 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.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 programu
Point
jest obliczany przezx ^ y
. Daje to bardzo małe rozproszenie w zakresie danych, a zatem przedziałyHashSet
są przepełnione - coś, co się nie dziejestring
, gdy rozproszenie skrótów jest znacznie większe.Możesz rozwiązać ten problem, implementując własną
Point
strukturę (trywialną) i używając lepszego algorytmu mieszającego dla oczekiwanego zakresu danych, np. Przesuwając współrzędne:Aby uzyskać dobre rady dotyczące kodów skrótów, przeczytaj wpis na blogu Erica Lipperta na ten temat .
źródło
GetHashCode
działa:unchecked(x ^ y)
podczasstring
gdy wygląda to na znacznie bardziej skomplikowane ..HashSet<long>()
zamiast tego ilist.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ś?list
kiedy skończysz go wypełniać?point
TheHashSet
będą wewnętrznie zadzwonićGetHashCode
i dla każdego z tych punktów o tej samej hashcode, zadzwoniEquals
aby ustalić, czy jest on już istniejePoint
gdy można stworzyć klasę, która implementujeIEqualityComparer<Point>
i zachowuje zgodność z innymi rzeczami, z którymi współpracuje,Point
jednocześnie czerpiąc korzyści z braku ubogichGetHashCode
i konieczności dołączaniaEquals()
.