HashSet vs. Kinerja daftar

Jelas bahwa kinerja pencarian HashSet<T>kelas generik lebih tinggi daripada List<T>kelas generik . Bandingkan saja kunci berbasis hash dengan pendekatan linier di List<T>kelas.

Namun menghitung kunci hash itu sendiri mungkin memerlukan beberapa siklus CPU, jadi untuk sejumlah kecil item pencarian linier dapat menjadi alternatif nyata untuk HashSet<T>.

Pertanyaan saya: di mana impas?

Untuk menyederhanakan skenario (dan bersikap adil) mari kita asumsikan bahwa List<T>kelas menggunakan metode elemen Equals()untuk mengidentifikasi item.

Banyak orang mengatakan bahwa setelah Anda mencapai ukuran di mana kecepatan sebenarnya merupakan masalah yang HashSet<T>akan selalu mengalahkan List<T>, tetapi itu tergantung pada apa yang Anda lakukan.

Katakanlah Anda memiliki List<T>yang hanya akan memiliki rata-rata 5 item di dalamnya. Lebih dari sejumlah besar siklus, jika satu item ditambahkan atau dihapus setiap siklus, Anda mungkin lebih baik menggunakan a List<T>.

Saya melakukan tes untuk ini pada mesin saya, dan, yah, itu harus sangat sangat kecil untuk mendapatkan keuntungan darinya List<T>. Untuk daftar string pendek, keuntungan hilang setelah ukuran 5, untuk objek setelah ukuran 20.

1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms

2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms

3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms

4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms

5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms

6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms

7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms

8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms

9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms

1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms

4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms

7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms

10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms

13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms

16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms

19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms

22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms

25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms

28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms

31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms

34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms

37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms

40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms

43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms

46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms

49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms

Berikut adalah data yang ditampilkan sebagai grafik:

Berikut kodenya:

static void Main(string[] args)
{
    int times = 10000000;


    for (int listSize = 1; listSize < 10; listSize++)
    {
        List<string> list = new List<string>();
        HashSet<string> hashset = new HashSet<string>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add("string" + i.ToString());
            hashset.Add("string" + i.ToString());
        }

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove("string0");
            list.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");


        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove("string0");
            hashset.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }


    for (int listSize = 1; listSize < 50; listSize+=3)
    {
        List<object> list = new List<object>();
        HashSet<object> hashset = new HashSet<object>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add(new object());
            hashset.Add(new object());
        }

        object objToAddRem = list[0];

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove(objToAddRem);
            list.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");



        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove(objToAddRem);
            hashset.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }

    Console.ReadLine();
}

Anda melihat ini salah. Ya, pencarian linear dari suatu Daftar akan mengalahkan HashSet untuk sejumlah kecil item. Namun perbedaan kinerja biasanya tidak masalah untuk koleksi sekecil itu. Ini umumnya koleksi besar yang harus Anda khawatirkan, dan di situlah Anda berpikir tentang Big-O . Namun, jika Anda telah mengukur hambatan nyata pada kinerja HashSet, maka Anda dapat mencoba membuat Daftar hybrid / HashSet, tetapi Anda akan melakukannya dengan melakukan banyak tes kinerja empiris - tidak mengajukan pertanyaan pada SO.

Tidak ada gunanya membandingkan dua struktur untuk kinerja yang berperilaku berbeda. Gunakan struktur yang menyampaikan maksud. Bahkan jika Anda mengatakan Anda List<T>tidak akan memiliki duplikat dan urutan iterasi tidak masalah membuatnya sebanding dengan a HashSet<T>, itu masih pilihan yang buruk untuk digunakan List<T>karena relatif lebih toleran terhadap kesalahan.

Yang mengatakan, saya akan memeriksa beberapa aspek kinerja lainnya,

+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |
|            | access |             |           |          |          |           |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T>    | O(1)   | O(n)        | O(n)      | O(1)*    | O(n)     | Lesser    |
| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)     | O(1)     | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+

• Meskipun penambahan adalah O (1) dalam kedua kasus, itu akan relatif lebih lambat di HashSet karena melibatkan biaya precomputing kode hash sebelum menyimpannya.

• Skalabilitas HashSet yang unggul memiliki biaya memori. Setiap entri disimpan sebagai objek baru bersama dengan kode hash-nya. Artikel ini mungkin memberi Anda ide.

Apakah menggunakan HashSet <> atau Daftar <> adalah bagaimana Anda perlu mengakses koleksi Anda . Jika Anda perlu menjamin urutan barang, gunakan Daftar. Jika tidak, gunakan HashSet. Biarkan Microsoft khawatir tentang penerapan algoritme dan objek hashing mereka.

HashSet akan mengakses item tanpa harus menyebutkan koleksi (kompleksitas O (1) atau di dekatnya), dan karena Daftar menjamin pesanan, tidak seperti HashSet, beberapa item harus disebutkan (kompleksitas O (n)).

Hanya berpikir saya akan berpadu dengan beberapa tolok ukur untuk skenario yang berbeda untuk menggambarkan jawaban sebelumnya:

1. Beberapa (12 - 20) string kecil (panjang antara 5 dan 10 karakter)
2. Banyak (~ 10K) string kecil
3. Beberapa string panjang (panjang antara 200 dan 1000 karakter)
4. Banyak (~ 5K) string panjang
5. Beberapa bilangan bulat
6. Banyak (~ 10K) bilangan bulat

Dan untuk setiap skenario, cari nilai yang muncul:

1. Di awal daftar ("mulai", indeks 0)
2. Menjelang awal daftar ("awal", indeks 1)
3. Di tengah daftar ("tengah", jumlah indeks / 2)
4. Menjelang akhir daftar ("terlambat", jumlah indeks-2)
5. Di akhir daftar ("end", indeks hitung-1)

Sebelum setiap skenario saya membuat daftar string acak berukuran acak, dan kemudian memasukkan setiap daftar ke hashset. Setiap skenario berjalan 10.000 kali, pada dasarnya:

(test kodesemu)

stopwatch.start
for X times
    exists = list.Contains(lookup);
stopwatch.stop

stopwatch.start
for X times
    exists = hashset.Contains(lookup);
stopwatch.stop

Output Sampel

Diuji pada Windows 7, Ram 12GB, 64 bit, Xeon 2.8GHz

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...

Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]


---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...

Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]


---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]


---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]


---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...

Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]


---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]

Titik impas akan tergantung pada biaya komputasi hash. Perhitungan hash bisa sepele, atau tidak ... :-) Selalu ada kelas System.Collections.Specialized.HybridDictionary untuk membantu Anda tidak perlu khawatir tentang titik impas.

Jawabannya, seperti biasa, adalah " Itu tergantung ". Saya berasumsi dari tag yang Anda bicarakan tentang C #.

Taruhan terbaik Anda adalah menentukan

1. Satu Set data
2. Persyaratan penggunaan

dan menulis beberapa test case.

Ini juga tergantung pada bagaimana Anda mengurutkan daftar (jika itu diurutkan sama sekali), perbandingan apa yang perlu dibuat, berapa lama operasi "Bandingkan" untuk objek tertentu dalam daftar, atau bahkan bagaimana Anda bermaksud menggunakan koleksi.

Secara umum, yang terbaik untuk dipilih bukan berdasarkan ukuran data yang Anda gunakan, tetapi bagaimana Anda akan mengaksesnya. Apakah Anda memiliki setiap bagian data yang terkait dengan string tertentu, atau data lainnya? Koleksi berbasis hash mungkin akan menjadi yang terbaik. Apakah urutan data yang Anda simpan penting, atau Anda perlu mengakses semua data pada saat yang sama? Daftar reguler mungkin lebih baik.

Tambahan:

Tentu saja, komentar saya di atas menganggap 'kinerja' berarti akses data. Sesuatu yang perlu dipertimbangkan: apa yang Anda cari ketika Anda mengatakan "kinerja"? Apakah nilai kinerja individu terlihat? Apakah manajemen set nilai besar (10000, 100000 atau lebih)? Apakah kinerja mengisi struktur data dengan data? Menghapus data? Mengakses bit data individual? Mengganti nilai? Iterasi atas nilai-nilai? Penggunaan memori? Kecepatan penyalinan data? Misalnya, Jika Anda mengakses data dengan nilai string, tetapi persyaratan kinerja utama Anda adalah penggunaan memori yang minimal, Anda mungkin memiliki masalah desain yang saling bertentangan.

Anda dapat menggunakan HybridDictionary yang secara otomatis mendeteksi titik putusnya, dan menerima nilai nol, menjadikannya sama pentingnya dengan HashSet.

Tergantung. Jika jawaban yang tepat benar-benar penting, lakukan beberapa profiling dan cari tahu. Jika Anda yakin tidak akan pernah memiliki lebih dari sejumlah elemen dalam set, buka Daftar. Jika nomornya tidak terikat, gunakan HashSet.

Tergantung pada apa yang Anda hashing. Jika kunci Anda bilangan bulat, Anda mungkin tidak perlu banyak item sebelum HashSet lebih cepat. Jika Anda mengetikkannya pada string maka itu akan lebih lambat, dan tergantung pada string input.

Tentunya Anda bisa menyiapkan tolok ukur dengan cukup mudah?

Salah satu faktor yang tidak Anda perhitungkan adalah kekokohan fungsi GetHashcode (). Dengan fungsi hash yang sempurna, HashSet jelas akan memiliki kinerja pencarian yang lebih baik. Tetapi karena fungsi hash berkurang, maka waktu pencarian HashSet juga akan berkurang.

Tergantung pada banyak faktor ... Implementasi daftar, arsitektur CPU, JVM, loop semantik, kompleksitas metode yang sama, dll ... Pada saat daftar menjadi cukup besar untuk secara efektif melakukan benchmark (1000+ elemen), biner berbasis hash pencarian mengalahkan pencarian linier tangan-down, dan perbedaannya hanya naik dari sana.

Semoga ini membantu!