Co kolekcja .NET zapewnia najszybsze wyszukiwanie

119

Mam 60k elementów, które należy sprawdzić na liście wyszukiwania 20k. Czy istnieje obiekt kolekcji (np. List, HashTable), który zapewnia wyjątkowo szybką metodę Contains()? Czy będę musiał napisać własną? Innymi słowy, jest domyślna metoda Contains() po prostu przeskanować każdy element lub używa lepszego algorytmu wyszukiwania.Co kolekcja .NET zapewnia najszybsze wyszukiwanie

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

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

Źródło

2009-06-17 Anonymous

Zawartość listy nie działa dla listy obiektów, ponieważ porównuje odwołania. – Fiur

Posortowane dane? Wyszukiwanie binarne - patrz @ Odpowiedź Marka. –

HashtTable bije nic do 2m elementów w moim doświadczeniu –

111

W najbardziej ogólnym przypadku należy rozważyć System.Collections.Generic.HashSet jako domyślną strukturę danych końskich koni roboczych, ponieważ uzyskanie stałej oceny zajmuje Contains.

Rzeczywista odpowiedź na pytanie "Jaka jest najszybciej dostępna do przeszukiwania kolekcja" zależy od konkretnego rozmiaru danych, uporządkowanego zbioru, kosztu mieszania i częstotliwości wyszukiwania.

Źródło

2009-06-17 19:38:51 Jimmy

+23

Uwaga: Nie zapomnij zastąpić funkcji hashcode. W celu zwiększenia wydajności, pregenerate hashcode w swoim konstruktorze. – Brian

@Brian: dobry punkt. Zakładałem (bez podstaw) Record.Key był typem wbudowanym. – Jimmy

Record.Key jest tylko długo –

Jeśli nie potrzebują uporządkowania, spróbuj HashSet<Record> (nowy do .NET 3.5)

Jeśli nie, użyj List<Record> i nazywają BinarySearch.

Źródło

2009-06-17 19:40:04 SLaks

Lub, w .NET> = 4, użyj [SortedSet] (http://msdn.microsoft.com/en-us/library/dd412070.aspx) – StriplingWarrior

Czy brałeś pod uwagę List.BinarySearch(item)?

Powiedziałeś, że twoja duża kolekcja jest już posortowana, więc wydaje się to idealną okazją? Wartość skrótu zdecydowanie byłaby najszybsza, ale powoduje to problemy i wymaga dużo więcej narzutów do przechowywania.

Źródło

2009-06-17 19:44:08 Mark

Masz rację, haszysz może przynieść niepożądane problemy, gdy używasz zmiennych obiektów jako klucza. – jmservera

Jeśli nie martwisz się piskaniem każdego ostatniego kroku wydajności, sugestia użycia HashSet lub wyszukiwania binarnego jest trwała. Twoje zbiory danych nie są na tyle duże, że będzie to stanowić problem w 99% przypadków.

Ale jeśli to tylko jeden z tysięcy razy, kiedy to zrobisz, a wydajność jest krytyczna (i udowodniono, że jest nie do przyjęcia z użyciem HashSet/binarnego wyszukiwania), z pewnością możesz napisać własny algorytm, który przechodził sortowane listy porównujące jak poszło. Każda lista będzie chodzona najwyżej raz, aw przypadkach patologicznych nie będzie zła (po przejściu tej trasy prawdopodobnie uznasz, że porównanie, zakładając, że jest to ciąg lub inna wartość nieintegralna, byłoby prawdziwym wydatkiem i że optymalizacja byłaby następnym krokiem).

Źródło

2009-06-17 19:48:22

Jeśli istnieje możliwość sortowania przedmiotów, istnieje o wiele szybszy sposób, aby to zrobić, a następnie wyszukiwanie kluczy w hoście lub hoście. Chociaż nie można sortować przedmiotów, nie można ich tak naprawdę umieścić w drzewie drzew.

W każdym razie, jeśli sortowanie sortuje obie listy, to tylko kwestia chodzenia listy odnośników 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

Źródło

2009-06-17 19:51:28 Qberticus

Tak, to prawda. Jeśli masz dwie posortowane listy, musisz przejść tylko raz. – denver

Jeśli używasz .NET 3.5 można dokonać czystsze kod za pomocą:

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

nie mam .Net 3.5 tutaj i tak jest to przetestowane. Opiera się na metodzie rozszerzenia. Nie oznacza to, że LookupCollection.Intersect(LargeCollection) prawdopodobnie nie jest taki sam jak LargeCollection.Intersect(LookupCollection) ... ten ostatni jest prawdopodobnie znacznie wolniejszy.

Zakłada LookupCollection jest HashSet

Źródło

2009-06-17 19:57:38 Brian

Przechowywać obu listach xiy posortowanych.

Jeśli x = y, wykonaj czynność, jeśli x < y, z wyprzedzeniem x, jeśli y < x, przesuń y, aż lista będzie pusta.

Czas pracy tego przecięcia jest proporcjonalna do min (wielkość (x), powierzchnia (y))

Nie uruchomić .Contains (pętla), jest proporcjonalna do x * Y, który jest o wiele gorszy.

Źródło

2009-06-17 20:10:50 clemahieu

+1 dla bardziej wydajnego algorytmu. Nawet jeśli listy są obecnie nieposortowane, lepiej byłoby najpierw je posortować, a następnie uruchomić ten algorytm. –

Czy środowisko wykonawcze nie będzie proporcjonalne do maksimum (rozmiar (x), rozmiar (y)) w najgorszym przypadku? Przykład: int [] x = {99,100}; int [] y = {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; –

Nie, ponieważ po ukończeniu mniejszego zestawu można dodać pozostałe elementy z większego zestawu, ponieważ są już posortowane. Myślę, że ten proces jest podobny do Merge Sort. –

Należy czytać this blog że prędkość testowany kilka różnych rodzajów zbiorów i metody dla każdego z zastosowaniem zarówno jedno- i wielowątkowych technik.

Zgodnie z wynikami, BinarySearch na liście i SortedList były najlepszymi wykonawcami, którzy nieustannie pracowali przy szyi, gdy patrzyli na coś jako "wartość".

Podczas korzystania z kolekcji, która pozwala na „klucze”, Dictionary, ConcurrentDictionary, Hashset i HashTables wykonywane najlepszy ogólny.

Źródło

2014-11-27 07:23:35

Co kolekcja .NET zapewnia najszybsze wyszukiwanie

Odpowiedz

Powiązane problemy