Mengapa HashSet <Point> jauh lebih lambat dari HashSet <string>?

Saya ingin menyimpan beberapa lokasi piksel tanpa mengizinkan duplikat, jadi hal pertama yang terlintas dalam pikiran adalah HashSet<Point>kelas yang serupa. Namun ini sepertinya sangat lambat dibandingkan dengan sesuatu seperti HashSet<string>.

Misalnya, kode ini:

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

membutuhkan waktu sekitar 22,5 detik.

Sementara kode berikut (yang bukan pilihan yang baik karena alasan yang jelas) hanya membutuhkan 1,6 detik:

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

Jadi, pertanyaan saya adalah:

• Apakah ada alasan untuk itu? Saya memeriksa jawaban ini , tetapi 22,5 detik jauh lebih banyak daripada angka yang ditunjukkan dalam jawaban itu.
• Apakah ada cara yang lebih baik untuk menyimpan poin tanpa duplikat?

Ada dua masalah kinerja yang disebabkan oleh struct Point. Sesuatu yang dapat Anda lihat ketika Anda menambah Console.WriteLine(GC.CollectionCount(0));kode tes. Anda akan melihat bahwa tes Point membutuhkan ~ 3720 koleksi tetapi tes string hanya membutuhkan ~ 18 koleksi. Tidak gratis. Ketika Anda melihat tipe nilai menginduksi begitu banyak koleksi maka Anda perlu menyimpulkan "uh-oh, terlalu banyak tinju".

Yang menjadi masalah adalah bahwa HashSet<T>perlu IEqualityComparer<T>untuk menyelesaikan tugasnya. Karena Anda tidak menyediakan satu, itu harus kembali ke satu dikembalikan oleh EqualityComparer.Default<T>(). Metode itu dapat melakukan pekerjaan yang baik untuk string, itu mengimplementasikan IEquatable. Tetapi tidak untuk Point, ini adalah tipe yang berasal dari .NET 1.0 dan tidak pernah mendapatkan cinta generik. Yang bisa dilakukan hanyalah menggunakan metode Object.

Masalah lainnya adalah bahwa Point.GetHashCode () tidak melakukan pekerjaan bintang dalam tes ini, terlalu banyak tabrakan, sehingga memalu Object.Equals () cukup banyak. String memiliki implementasi GetHashCode yang sangat baik.

Anda dapat menyelesaikan kedua masalah dengan menyediakan HashSet dengan pembanding yang baik. Seperti yang ini:

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

Dan gunakan itu:

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

Dan sekarang sekitar 150 kali lebih cepat, dengan mudah mengalahkan tes string.

Alasan utama untuk penurunan kinerja adalah semua tinju terjadi (seperti yang sudah dijelaskan dalam jawaban Hans Passant ).

Terlepas dari itu, algoritma kode hash memperburuk masalah, karena menyebabkan lebih banyak panggilan Equals(object obj)sehingga meningkatkan jumlah konversi tinju.

Perhatikan juga bahwa kode hashPoint dihitung oleh x ^ y. Ini menghasilkan dispersi yang sangat sedikit dalam rentang data Anda, dan oleh karena itu ember dari HashSetpopulasi berlebih - sesuatu yang tidak terjadi string, di mana dispersi hash jauh lebih besar.

Anda dapat memecahkan masalah itu dengan mengimplementasikan Pointstruct Anda sendiri (sepele) dan menggunakan algoritma hash yang lebih baik untuk rentang data yang Anda harapkan, misalnya dengan menggeser koordinat:

(x << 16) ^ y

Untuk beberapa saran yang baik ketika datang ke kode hash, baca posting blog Eric Lippert pada subjek .