HashSet vs. wydajność listy

Oczywiste jest, że wydajność wyszukiwania HashSet<T>klasy ogólnej jest wyższa niż List<T>klasy ogólnej . Wystarczy porównać klucz oparty na haszowaniu z podejściem liniowym w List<T>klasie.

Jednak obliczenie klucza skrótu może zająć kilka cykli procesora, więc dla niewielkiej liczby elementów wyszukiwanie liniowe może być realną alternatywą dla HashSet<T>.

Moje pytanie: gdzie jest rentowność?

Aby uprościć scenariusz (i być uczciwym) załóżmy, że List<T>klasa używa metody elementu Equals()do identyfikacji elementu.

Wiele osób mówi, że gdy dojdziesz do rozmiaru, w którym prędkość jest tak naprawdę problemem, HashSet<T>który zawsze będzie bić List<T>, ale zależy to od tego, co robisz.

Powiedzmy, że masz coś, List<T>co będzie zawierało średnio tylko 5 przedmiotów. W przypadku dużej liczby cykli, jeśli jeden element jest dodawany lub usuwany w każdym cyklu, lepiej jest użyć List<T>.

Zrobiłem test na tym na moim komputerze i, cóż, musi być bardzo, bardzo mały, aby uzyskać przewagę List<T>. W przypadku listy krótkich ciągów korzyść zniknęła po rozmiarze 5, w przypadku obiektów po rozmiarze 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

Oto dane wyświetlane jako wykres:

Oto kod:

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

Patrzysz na to źle. Tak, liniowe wyszukiwanie listy przebije zestaw HashSet dla niewielkiej liczby elementów. Ale różnica wydajności zwykle nie ma znaczenia dla tak małych kolekcji. Zasadniczo są to duże kolekcje, o które musisz się martwić i właśnie o tym myślisz w kategoriach Big-O . Jeśli jednak zmierzyłeś prawdziwe wąskie gardło w wydajności HashSet, możesz spróbować utworzyć hybrydowy List / HashSet, ale zrobisz to, przeprowadzając wiele empirycznych testów wydajności - nie zadając pytań na temat SO.

To w zasadzie bezcelowe porównanie dwóch struktur wydajności , które zachowują się inaczej. Użyj struktury, która przekazuje zamiar. Nawet jeśli powiesz, List<T>że nie będziesz miał duplikatów, a kolejność iteracji nie ma znaczenia, czyniąc go porównywalnym z HashSet<T>, jest to nadal zły wybór, List<T>ponieważ jest stosunkowo mniej odporny na błędy.

To powiedziawszy, zbadam kilka innych aspektów wydajności,

+------------+--------+-------------+-----------+----------+----------+-----------+
| 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** |
+------------+--------+-------------+-----------+----------+----------+-----------+

• Mimo że dodawanie to O (1) w obu przypadkach, w HashSet będzie stosunkowo wolniejsze, ponieważ wiąże się to z kosztem wstępnego obliczenia kodu skrótu przed jego zapisaniem.

• Doskonała skalowalność HashSet ma koszt pamięci. Każdy wpis jest zapisywany jako nowy obiekt wraz z kodem skrótu. Ten artykuł może dać ci pomysł.

To, czy chcesz użyć HashSet <> czy List <>, sprowadza się do tego, jak potrzebujesz uzyskać dostęp do swojej kolekcji . Jeśli chcesz zagwarantować kolejność przedmiotów, skorzystaj z Listy. Jeśli nie, użyj HashSet. Niech Microsoft martwi się implementacją algorytmów i obiektów mieszających.

Zestaw HashSet będzie uzyskiwał dostęp do elementów bez konieczności wyliczania kolekcji (złożoność O (1) lub w jej pobliżu), a ponieważ Lista gwarantuje porządek, w przeciwieństwie do zestawu HashSet, niektóre elementy będą musiały zostać wyliczone (złożoność O (n)).

Pomyślałem, że włączyłem kilka testów porównawczych dla różnych scenariuszy, aby zilustrować poprzednie odpowiedzi:

1. Kilka (12-20) małych ciągów znaków (długość od 5 do 10 znaków)
2. Wiele (~ 10K) małych ciągów
3. Kilka długich ciągów znaków (długość od 200 do 1000 znaków)
4. Wiele (~ 5K) długich łańcuchów
5. Kilka liczb całkowitych
6. Wiele liczb całkowitych (~ 10 000)

I dla każdego scenariusza wyszukaj wartości, które się pojawią:

1. Na początku listy („start”, indeks 0)
2. Blisko początku listy („wczesny”, indeks 1)
3. Na środku listy („środkowy”, liczba indeksów / 2)
4. Pod koniec listy („późno”, liczba indeksów-2)
5. Na końcu listy („end”, liczba indeksów-1)

Przed każdym scenariuszem wygenerowałem listy losowych ciągów o losowych rozmiarach, a następnie podałem każdą listę do zestawu skrótów. Każdy scenariusz był uruchamiany 10 000 razy, zasadniczo:

(pseudokod testowy)

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

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

Przykładowe dane wyjściowe

Testowany na Windows 7, 12 GB RAM, 64-bitowy, 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]

Próg rentowności będzie zależeć od kosztu obliczenia skrótu. Obliczenia za pomocą skrótu mogą być trywialne lub nie ... :-) Zawsze istnieje klasa System.Collections.Specialized.HybridDictionary, aby pomóc Ci nie martwić się o punkt progowy.

Odpowiedź jak zawsze brzmi „ to zależy ”. Zakładam, że z tagów mówisz o C #.

Najlepszym rozwiązaniem jest ustalenie

1. Zestaw danych
2. Wymagania dotyczące użytkowania

i napisz kilka przypadków testowych.

Zależy to również od sposobu sortowania listy (jeśli w ogóle jest posortowana), jakiego rodzaju porównań należy wykonać, czasu operacji „Porównaj” dla konkretnego obiektu na liście, a nawet od tego, jak zamierzasz użyć kolekcja.

Ogólnie rzecz biorąc, najlepszy do wyboru nie tyle zależy od wielkości danych, z którymi pracujesz, ale raczej od tego, jak zamierzasz uzyskać do nich dostęp. Czy każdy element danych jest powiązany z określonym ciągiem lub innymi danymi? Kolekcja oparta na haszowaniu prawdopodobnie byłaby najlepsza. Czy kolejność przechowywanych danych jest ważna, czy też będziesz musiał uzyskać dostęp do wszystkich danych w tym samym czasie? Zwykła lista może być lepsza.

Dodatkowy:

Oczywiście moje powyższe komentarze zakładają, że „wydajność” oznacza dostęp do danych. Coś jeszcze do rozważenia: czego szukasz, kiedy mówisz „wydajność”? Czy indywidualna wartość wydajności jest sprawdzana? Czy to zarządzanie dużymi (10000, 100000 lub więcej) zestawami wartości? Czy to wydajność wypełniania struktury danych danymi? Usuwasz dane? Uzyskujesz dostęp do poszczególnych bitów danych? Zastępujesz wartości? Iteracja po wartościach? Zużycie pamięci? Szybkość kopiowania danych? Na przykład, jeśli uzyskujesz dostęp do danych za pomocą wartości ciągu, ale głównym wymaganiem dotyczącym wydajności jest minimalne zużycie pamięci, możesz mieć konflikt problemów projektowych.

Możesz użyć HybridDictionary, który automatycznie wykrywa punkt przerwania i akceptuje wartości zerowe, dzięki czemu jest zasadniczo taki sam jak zestaw HashSet.

To zależy. Jeśli dokładna odpowiedź naprawdę ma znaczenie, wykonaj profilowanie i dowiedz się. Jeśli masz pewność, że nigdy nie będziesz mieć więcej niż pewną liczbę elementów w zestawie, skorzystaj z Listy. Jeśli numer jest nieograniczony, użyj zestawu HashSet.

Zależy od tego, co hashujesz. Jeśli twoje klucze są liczbami całkowitymi, prawdopodobnie nie potrzebujesz bardzo wielu elementów, zanim zestaw HashSet będzie szybszy. Jeśli wpisujesz go w ciągu, będzie on wolniejszy i zależy od ciągu wejściowego.

Z pewnością mógłbyś łatwo podnieść poziom odniesienia?

Jednym z czynników, których nie bierzesz pod uwagę, jest niezawodność funkcji GetHashcode (). Dzięki doskonałej funkcji skrótu HashSet będzie miał wyraźnie lepszą wydajność wyszukiwania. Jednak wraz ze zmniejszaniem się funkcji skrótu zmniejsza się czas wyszukiwania HashSet.

Zależy od wielu czynników ... Implementacja listy, architektura procesora, JVM, semantyka pętli, złożoność metody równości itp. Do czasu, gdy lista staje się wystarczająco duża, aby skutecznie przeprowadzić testy porównawcze (ponad 1000 elementów), binarny oparty na haszu wyszukiwania pokonują liniowe wyszukiwania, a różnica rośnie tylko od tego miejsca.

Mam nadzieję że to pomoże!