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.
.net
performance
collections
list
hash
Michael Damatov
źródło
źródło
Odpowiedzi:
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.Oto dane wyświetlane jako wykres:
Oto kod:
źródło
List<T>
przypadku silnika gry, a ponieważ zwykle będę mieć dużą liczbę obiektów, ten rodzaj kolekcji byłby idealny.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.
źródło
when small collection becomes large enough to worry about HashSet vs List?
dziesiątek, dziesiątek tysięcy, miliardów elementów?HashSet<T>
. W małych przypadkach, w którychList<T>
może być szybciej, różnica jest nieznaczna . ”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 zHashSet<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,
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ł.
źródło
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)).
źródło
List
preferowane jest a , ponieważ możesz zapamiętać indeks - taką sytuację możesz wykonać opisują.Pomyślałem, że włączyłem kilka testów porównawczych dla różnych scenariuszy, aby zilustrować poprzednie odpowiedzi:
I dla każdego scenariusza wyszukaj wartości, które się pojawią:
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)
Przykładowe dane wyjściowe
Testowany na Windows 7, 12 GB RAM, 64-bitowy, Xeon 2.8GHz
źródło
List
nadal zajmuje tylko 0,17 milisekundy, aby wykonać pojedyncze wyszukiwanie i prawdopodobnie nie będzie wymagać zamiany,HashSet
dopóki częstotliwość wyszukiwania nie osiągnie absurdalnego poziomu. Do tego czasu korzystanie z Listy zwykle stanowi najmniejszy problem.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.
źródło
Odpowiedź jak zawsze brzmi „ to zależy ”. Zakładam, że z tagów mówisz o C #.
Najlepszym rozwiązaniem jest ustalenie
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.
źródło
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.
źródło
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.
źródło
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?
źródło
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.
źródło
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!
źródło