C# HashSet <T> wydajność wyszukiwania (w porównaniu do ObservableCollection <T>)?

Question

C# ogólna HashSet < T> wydajność wyszukiwania powinna wynosić O (1), a wydajność wyszukiwania ObservableCollection < T> powinna wynosić O (n).

Mam dużą liczbę unikalnych elementów, każdy element ma właściwość DateTime, która nie jest unikalna.

Każdy element oblicza swój HashCode, po prostu zwracając jego DateTime.GetHashCode().

Teraz chcę uzyskać podzbiór moich danych, np. Wszystkie elementy, które mają datę, która jest w okresie od marca 2012 do czerwca 2012.

var result = from p in this.Elements 
       where p.Date >= new DateTime(2012, 03, 01) && 
         p.Date <= new DateTime(2012, 30, 06 
       select p; 

Jeżeli uruchomić kwerendy LINQ na kolekcję 300.000 elementów, trwa ~ 25 ms powrót 80 elementów, które są w danym przedziale - Nie ma znaczenia, czy używam HashSet < T> czy ObservableCollection < T>.

Jeśli przejdę wszystkie elementy ręcznie i sprawdzę je, zajmuje to samo, ~ 25 ms.

Ale znam HashCode wszystkich dat, które są w podanym zakresie. Czy można uzyskać wszystkie elementy o podanych HashCodes z mojego HashSet < T>? Myślę, że byłoby znacznie szybciej ...

Czy można przyspieszyć zapytanie LINQ? Zakładam, że nie korzysta ze specjalnych zdolności mojego HashSet < T>?

Answer 1

Jak już wskazano, zestaw hash jest bardzo skuteczny w określaniu, czy dany skrót jest w zestawie. Twoje zapytanie wykorzystuje fakt, że narzędzie hashset implementuje IEnumerable do iterowania w całym zestawie i wykonania porównania dat. W ogóle nie użyje haszy. Z tego powodu ręczna metoda zajmuje tyle czasu, co zapytanie.

Nie można uzyskać elementu opartego na haszyszu z hashitu, można jedynie przetestować obecność elementu w zestawie. Słownik jest tym, czego potrzebujesz, jeśli chcesz go zdobyć (ma się wrażenie, że go nie masz).

Zdecyduj, co musisz zrobić z danymi i użyj struktury, która jest zoptymalizowana pod kątem tego. Może to być twoja własna klasa, która utrzymuje wiele wewnętrznych struktur, z których każda jest skuteczna w jednej rzeczy (jak w przypadku wyszukiwania zakresów, a druga w celu sprawdzenia przez istnienie według wielu pól), lub może istnieć istniejąca struktura, która pasuje do twoich potrzeb. Ale nie wiedząc, co to jest, co chcesz zrobić ze swoimi danymi, trudno jest im doradzić.

Kolejną rzeczą, którą należy rozważyć, jest to, czy optymalizujesz się przedwcześnie. Jeśli 25ms do wyszukiwania ręcznie jest wystarczająco szybkie, to może jakaś struktura, która implementuje IEnumerable będzie wystarczająco dobra. W takim przypadku możesz wybrać jeden na podstawie innych kryteriów, których potrzebujesz.

Answer 2

Nie używasz właściwej struktury danych. Powinieneś używać czegoś w rodzaju posortowanej listy (posortowanej według właściwości Date), w której możesz następnie wyszukać binarnie początek i koniec zakresu.