HashSet vs. wydajność listy

404

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.

Michael Damatov
źródło
7
Jeśli naprawdę chcesz zminimalizować czas wyszukiwania, rozważ również tablice i tablice sortowane. Aby poprawnie odpowiedzieć na to pytanie, potrzebny jest test porównawczy, ale musisz powiedzieć nam więcej o T. Ponadto na wydajność HashSet może wpływać czas działania T.GetHashCode ().
Eldritch Conundrum

Odpowiedzi:

818

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:

wprowadź opis zdjęcia tutaj

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();
}
innominate227
źródło
8
Dziękuję bardzo! To świetne wytłumaczenie, szukałem czegoś, co można dodawać i usuwać szybciej niż w List<T>przypadku silnika gry, a ponieważ zwykle będę mieć dużą liczbę obiektów, ten rodzaj kolekcji byłby idealny.
redcodefinal
17
W systemie .NET istnieje kolekcja, która przełącza się między listą a implementacją hastable w zależności od liczby zawartych w niej elementów: HybridDictionary .
MgSam,
8
Wydaje się, że stwardnienie rozsiane porzuciło tę myśl, ponieważ ma dostępną tylko wersję ogólną.
MgSam,
47
Choć pełna jest ta odpowiedź, nie odpowiada ona na pierwotne pytanie dotyczące wydajności wyszukiwania listy w porównaniu z funkcją mieszania. Testujesz, jak szybko możesz je wstawiać i usuwać, co zajmuje znacznie więcej czasu i różni się wydajnością niż wyszukiwanie. Spróbuj ponownie, używając .Contains, a Twój wykres znacznie się zmieni.
Robert McKee,
5
@hypehuman CPU nie może pracować bezpośrednio na danych w pamięci systemowej, ale pobiera dane z pamięci do pamięci podręcznej, aby dalej pracować. Istnieje znaczne opóźnienie między żądaniem przeniesienia pamięci a faktyczną pamięcią, więc procesor często żąda przeniesienia większej części ciągłej pamięci jednocześnie. Chodzi o to, że pamięć potrzebna do następnej instrukcji jest prawdopodobnie bardzo bliska pamięci używanej przez poprzednią instrukcję, a zatem często znajduje się już w pamięci podręcznej. Kiedy twoje dane są rozproszone po całej pamięci, szansa na szczęście jest zmniejszona.
Roy T.
70

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.

Eloff
źródło
5
duże kolekcje, o które musisz się martwić . Możemy przedefiniować to pytanie pod względem when small collection becomes large enough to worry about HashSet vs List?dziesiątek, dziesiątek tysięcy, miliardów elementów?
om-nom-nom
8
Nie, zobaczysz znaczną różnicę wydajności powyżej kilkuset elementów. Chodzi o to, że zawsze używasz HashSet, jeśli robisz rodzaje dostępu, w których HashSet jest dobry (np. Jest elementem X w zestawie). Jeśli twoja kolekcja jest tak mała, że ​​Lista jest szybsza, bardzo rzadko te wyszukiwania są właściwie wąskim gardłem w twojej aplikacji. Jeśli potrafisz zmierzyć to jako jeden, możesz spróbować go zoptymalizować - ale w przeciwnym razie marnujesz swój czas.
Eloff
15
Co zrobić, jeśli masz małą kolekcję, która wielokrotnie trafia w pętlę? To nie jest rzadki scenariusz.
dan-gph
3
@ om-nom-nom - Myślę, że chodzi o to, że nie ma znaczenia, gdzie jest punkt krytyczny, ponieważ: „Jeśli wydajność jest zmartwieniem, użyj HashSet<T>. W małych przypadkach, w których List<T>może być szybciej, różnica jest nieznaczna . ”
Scott Smith,
66

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ł.

nawfal
źródło
11
Moje pytanie (sześć lat temu) nie dotyczyło wyników teoretycznych .
Michael Damatov
1
HashSet pozwala na losowy dostęp z ElementAt () i myślę, że byłby to czas O (n). Być może możesz umieścić w tabeli, czy każda kolekcja zezwala na duplikaty (np. Listy robią, ale hashsety nie).
Dan W
1
@ DanW w tabeli porównuję czystą wydajność, a nie cechy behawioralne. Dzięki za wskazówkę ElementAt.
nawfal
1
ElementAt to tylko rozszerzenie LINQ. Nie robi nic, czego nie można zrobić i lepiej zoptymalizować w innej metodzie, którą sam dodajesz. Myślę, że tabela miała większy sens bez uwzględnienia ElementAt, ponieważ wszystkie inne metody istnieją w tych klasach wyraźnie.
Dinerdo
Dzięki za tę tabelę, w moim przypadku użycia muszę dodawać i usuwać cele do zapełnionej kolekcji za każdym razem, gdy są one włączane / wyłączane, co pomogło mi dokonać właściwego wyboru (HashSet).
Casey Hofland
50

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)).

rdzeń
źródło
Lista potencjalnie może obliczyć przesunięcie dla określonego elementu na podstawie jego indeksu (ponieważ wszystkie elementy są tego samego typu i potencjalnie zajmują ten sam rozmiar pamięci). Lista nie jest więc potrzebna, wylicza jej elementy
Lu55
@ Lu55 - Pytanie dotyczy wyszukiwania elementu w kolekcji. Typowy scenariusz polega na tym, że kolekcja jest dynamiczna - elementy mogły zostać dodane lub usunięte od ostatniego wyszukiwania danego elementu - więc indeks nie ma znaczenia (ponieważ zostanie zmieniony). Jeśli masz kolekcję statyczną (która nie zmieni się podczas wykonywania obliczeń) lub elementy nigdy nie są usuwane i zawsze są dodawane na końcu, wtedy Listpreferowane jest a , ponieważ możesz zapamiętać indeks - taką sytuację możesz wykonać opisują.
ToolmakerSteve
Możesz użyć SortedSet, jeśli chcesz posortować HashSet. Nadal znacznie szybciej niż lista.
live-love
25

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]
drzaus
źródło
7
Ciekawy. Dzięki za uruchomienie tego. Niestety podejrzewam, że te dyskusje powodują niepotrzebne refaktoryzacje. Mamy nadzieję, że dla większości ludzi na wynos jest to, że w twoim absolutnie najgorszym scenariuszu Listnadal zajmuje tylko 0,17 milisekundy, aby wykonać pojedyncze wyszukiwanie i prawdopodobnie nie będzie wymagać zamiany, HashSetdopóki częstotliwość wyszukiwania nie osiągnie absurdalnego poziomu. Do tego czasu korzystanie z Listy zwykle stanowi najmniejszy problem.
Paul Walls,
Na razie nie są to rzeczywiste informacje. A może pierwotnie jest źle ... Właśnie sprawdziłem małe wartości od 2 do 8 znaków. List / HashSet utworzono dla każdej 10 wartości ... HashSet wolniej o 30% ... Jeśli używana jest pojemność na Liście, różnica wynosi nawet ~ 40%. HashSet staje się szybszy o 10% tylko wtedy, gdy lista nie ma określonej pojemności i sprawdza każdą wartość przed dodaniem całej listy.
Maxim
Jeśli liczba przedmiotów spadnie do 4, Lista ponownie wygrywa nawet w najgorszym scenariuszu (z różnicą 10%). Nie polecam więc używać HashSet do niewielkiej kolekcji ciągów (powiedzmy <20). I to różni się od „kilku małych” testów.
Maxim
1
@Maxim nie może powiedzieć, że moje wyniki są „złe” - tak się stało na moim komputerze. YMMV. W rzeczywistości po prostu uruchomiłem je ponownie ( gist.github.com/zaus/014ac9b5a78b267aa1643d63d30c7554 ) na nowym komputerze półprzewodnikowym Win10 4.0GHz 16 GB i uzyskałem podobne wyniki. Widzę, że wydajność mieszania była bardziej spójna bez względu na to, gdzie znajdował się klucz wyszukiwania i jak duża była lista, podczas gdy wydajność listy zmieniała się gwałtownie, od lepszej do ponad 300 razy wolniejszej. Ale, jak początkowo skomentował PaulWalls, mówimy poważnie #microoptimization.
drzaus
@Maxim w celach informacyjnych: dotnetfiddle.net/5taRDd - zachęcamy do zabawy.
drzaus
10

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.

Walden Leverich
źródło
1
Musisz także wziąć pod uwagę koszt przeprowadzenia porównania. W przypadku Contains (T) HashSet dokona porównania, aby sprawdzić, czy nie ma kolizji Hash względem Listy, która porówna każdy element, na który patrzy, zanim znajdzie właściwy. Musisz także wziąć pod uwagę rozkład skrótów generowanych przez T.GetHashCode (), tak jakby to zawsze zwracało tę samą wartość, że HashSet zasadniczo robi to samo, co List.
Martin Brown,
6

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.

Robert P.
źródło
5

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.

Muis
źródło
1
Poparłem to za pomysł, ale nikt nigdy nie powinien tego dzisiaj używać. Powiedz nie nie-rodzajowym. Również słownik jest kluczowym odwzorowaniem, zestaw nie jest.
nawfal
4

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.

Adam Rosenfield
źródło
3

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?

Piotr
źródło
3

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.

JaredPar
źródło
0

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!

Kyle
źródło
1
JVM ... lub CLR :-)
bvgheluwe