Jaka kolekcja .NET zapewnia najszybsze wyszukiwanie

Mam 60 tys. Pozycji, które należy porównać z listą wyszukiwania 20 tys. Czy istnieje obiekt kolekcji (np List, HashTable), który zapewnia exceptionly szybki Contains()sposób? A może będę musiał napisać własne? Innymi słowy, jest to domyślna Contains()metoda, polegająca na skanowaniu każdego elementu lub korzystaniu z lepszego algorytmu wyszukiwania.

foreach (Record item in LargeCollection)
{
    if (LookupCollection.Contains(item.Key))
    {
       // Do something
    }
}

Uwaga . Lista odnośników jest już posortowana.

W najbardziej ogólnym przypadku należy traktować System.Collections.Generic.HashSetjako domyślną strukturę danych „Zawiera” konia roboczego, ponieważ ocena wymaga ciągłego czasu Contains.

Rzeczywista odpowiedź na pytanie „Jaki zbiór można najszybciej przeszukiwać” zależy od określonego rozmiaru danych, uporządkowania, kosztu haszowania i częstotliwości wyszukiwania.

Jeśli nie potrzebujesz składania zamówień, wypróbuj HashSet<Record>(nowość w .Net 3.5)

Jeśli tak, użyj List<Record>i zadzwoń BinarySearch.

Czy rozważałeś List.BinarySearch(item)?

Powiedziałeś, że twoja duża kolekcja jest już posortowana, więc wydaje się, że to idealna okazja? Hash byłby zdecydowanie najszybszy, ale powoduje to własne problemy i wymaga znacznie więcej na przechowywanie.

Powinieneś przeczytać tego bloga, który przyspieszył przetestowanie kilku różnych typów kolekcji i metod dla każdego z nich przy użyciu technik jedno- i wielowątkowych.

Zgodnie z wynikami, BinarySearch on a List i SortedList były najlepszymi wynikami, które nieustannie szły łeb w łeb, szukając czegoś jako „wartości”.

W przypadku korzystania z kolekcji, która zezwala na „klucze”, Dictionary, ConcurrentDictionary, Hashset i HashTables wypadły najlepiej.

Zachowaj obie listy x i y w porządku posortowanym.

Jeśli x = y, wykonaj swoją akcję, jeśli x <y, przejdź do przodu x, jeśli y <x, przejdź do przodu o y, aż którakolwiek z list będzie pusta.

Czas wykonania tego przecięcia jest proporcjonalny do min (rozmiar (x), rozmiar (y))

Nie uruchamiaj pętli .Contains (), jest to proporcjonalne do x * y, co jest znacznie gorsze.

Jeśli możesz posortować swoje elementy, istnieje znacznie szybszy sposób na zrobienie tego niż wyszukiwanie kluczy w drzewie hashtable lub b-tree. Chociaż jeśli nie możesz sortować przedmiotów, tak naprawdę nie możesz ich umieścić w drzewie b.

W każdym razie, jeśli można sortować obie listy, to jest to tylko kwestia chodzenia po liście wyszukiwania w kolejności.

Walk lookup list
   While items in check list <= lookup list item
     if check list item = lookup list item do something
   Move to next lookup list item

Jeśli używasz .Net 3.5, możesz stworzyć bardziej przejrzysty kod za pomocą:

foreach (Record item in LookupCollection.Intersect(LargeCollection))
{
  //dostuff
}

Nie mam tutaj .Net 3.5, więc nie jest to testowane. Opiera się na metodzie rozszerzenia. Nie LookupCollection.Intersect(LargeCollection)to chyba to nie to samo, co LargeCollection.Intersect(LookupCollection)... ten drugi jest prawdopodobnie znacznie wolniejszy.

Zakłada się, że LookupCollection jest plikiem HashSet

Jeśli nie martwisz się pisaniem każdego ostatniego fragmentu wydajności, sugestia użycia HashSet lub wyszukiwania binarnego jest solidna. Twoje zbiory danych po prostu nie są na tyle duże, że będzie to problem w 99% przypadków.

Ale jeśli to tylko jeden z tysięcy razy, gdy zamierzasz to zrobić, a wydajność jest krytyczna (i udowodniono, że jest nie do przyjęcia przy użyciu HashSet / wyszukiwania binarnego), z pewnością możesz napisać własny algorytm, który przeszedł posortowane listy, wykonując porównania na bieżąco. Każdą listę można by przejść najwyżej raz, aw przypadkach patologicznych nie byłaby zła (po przejściu tej trasy prawdopodobnie okaże się, że porównanie, zakładając, że jest to ciąg lub inna wartość niecałkowita, byłoby rzeczywistym wydatkiem i że optymalizacja byłaby następnym krokiem).