Różnica między Lookup () a Dictionary (Of list ())

165

Próbuję ogarnąć głowę, które struktury danych są najbardziej wydajne i kiedy / gdzie ich użyć.

Możliwe, że po prostu nie rozumiem struktur wystarczająco dobrze, ale czym ILookup(of key, ...)różni się od Dictionary(of key, list(of ...))?

Również gdzie chciałbym użyć ILookupi gdzie byłoby to bardziej wydajne pod względem szybkości programu / pamięci / dostępu do danych itp.?

John Bustos
źródło
1
można też chcieć zobaczyć, co-jest-punktem-wyszukiwaniatkey-telement
nawfal

Odpowiedzi:

255

Dwie istotne różnice:

  • Lookupjest niezmienna. Tak :) (Przynajmniej uważam, że konkretna Lookupklasa jest niezmienna, a ILookupinterfejs nie zapewnia żadnych mutujących elementów członkowskich. Oczywiście mogą istnieć inne modyfikowalne implementacje.)
  • Kiedy wyszukujesz klucz, którego nie ma w wyszukiwaniu, zamiast a KeyNotFoundException. (Dlatego nie ma TryGetValue, AFAICR.)

Prawdopodobnie będą one równoważne pod względem wydajności - na przykład wyszukiwanie może korzystać Dictionary<TKey, GroupingImplementation<TValue>>zza kulis. Wybierz między nimi w zależności od swoich wymagań. Osobiście uważam, że wyszukiwanie jest zwykle lepiej dopasowane niż a Dictionary<TKey, List<TValue>>, głównie z powodu dwóch pierwszych punktów powyżej.

Należy pamiętać, że jako szczegółów realizacji, konkretna realizacja IGrouping<,>, który jest używany dla wartości narzędzi IList<TValue>, co oznacza, że jest wydajny w użyciu Count(), ElementAt()etc.

Jon Skeet
źródło
Jeśli nieistniejące wyszukiwanie klucza skutkuje pustą sekwencją, a nie wyjątkiem, to bardzo nie można go użyć jako zbioru imo ogólnego przeznaczenia. Jest to trochę w porządku w przypadku niezmiennej kolekcji, która jest produktem ubocznym zapytań linq.
nawfal
@nawfal - dokładnie do tego służą Lookups. From msdn : „Możesz utworzyć wystąpienie Lookup <TKey, TElement>, wywołując ToLookup na obiekcie, który implementuje IEnumerable <T>.”
Niall Connaughton
50

Ciekawe, że nikt nie określił rzeczywistej największej różnicy (pobrane bezpośrednio z MSDN ):

Wyszukiwanie przypomina słownik. Różnica polega na tym, że słownik odwzorowuje klucze na pojedyncze wartości, podczas gdy odnośnik odwzorowuje klucze na zbiory wartości.

Mladen Mihajlovic
źródło
51
Sprawdź pytanie: chodzi o różnicę między Lookup <TKey, TValue> a Dictionary <TKey, List <TValue>>, więc ta różnica jest już wyraźna.
Martao
5
@Martao niektórzy ludzie napotykają to pytanie podczas wyszukiwania w Google, aby zrozumieć różnicę między wyszukiwaniami a słownikami. Ta odpowiedź jest naprawdę przydatna.
jakubiszon
34

Zarówno a, jak Dictionary<Key, List<Value>>i a Lookup<Key, Value>logicznie mogą przechowywać dane zorganizowane w podobny sposób i oba mają tę samą wydajność. Główną różnicą jest to, że a Lookupjest niezmienny: nie ma Add()metod ani publicznego konstruktora (i jak wspomniał Jon, można bez wyjątku zapytać o nieistniejący klucz i mieć klucz jako część grupowania).

To, którego używasz, naprawdę zależy od tego, jak chcesz ich używać. Jeśli utrzymujesz mapę klucza do wielu wartości, która jest stale modyfikowana, Dictionary<Key, List<Value>>to prawdopodobnie jest lepsze, ponieważ jest zmienne.

Jeśli jednak masz sekwencję danych i potrzebujesz tylko widoku tylko do odczytu uporządkowanych według klucza, wyszukiwanie jest bardzo łatwe do skonstruowania i daje migawkę tylko do odczytu.

James Michael Hare
źródło
11

Podstawowa różnica między ILookup<K,V>a a Dictionary<K, List<V>>polega na tym, że słownik jest zmienny; możesz dodawać lub usuwać klucze, a także dodawać lub usuwać elementy z przeszukiwanej listy. ILookupJest niezmienne i nie mogą być zmienione po utworzeniu.

Podstawowa implementacja obu mechanizmów będzie taka sama lub podobna, więc ich szybkość wyszukiwania i zużycie pamięci będą w przybliżeniu takie same.

Servy
źródło
1
@JohnBustos Jeśli chodzi o wydajność, nie. To czysto logiczne. Możesz przekazywać odniesienia do struktury wokół ciebie i nie martwić się, że ktoś inny zmodyfikuje ją spod ciebie. Możesz założyć, że jest niezmienne, że nie możesz, gdyby było zmienne.
Servy
Dzięki, Servy, to bardzo dobry punkt, gdy często podajesz tak wiele zmiennych ByRef - przynajmniej tej, której na pewno nie możesz zmodyfikować. Dzięki!
John Bustos
2
@JohnBustos Pamiętaj, że domyślną metodą przekazywania parametru metody jest wartość, musisz jawnie dodać byref, a to powinno być wykonywane dość rzadko. Te struktury danych są klasami, co czyni je typami referencyjnymi, więc przekazanie wartości jest wartością odwołania, dlatego przekazanie jej do innej metody może spowodować widoczne zmiany w obiekcie wywołującym.
Servy
Dzięki, Servy, to otwiera dla mnie zupełnie nową puszkę robaków, biorąc pod uwagę to, co robiłem :), ale rozumiem, co mówisz. Dzięki!!
John Bustos
Czy wiesz pod okładkami, czy Lookup używa hashbuckets jako klucza?
paparazzo
10

Inną różnicą, o której jeszcze nie wspomniano, jest to, że Lookup () obsługuje klucze puste :

Klasa Lookup implementuje interfejs ILookup. Wyszukiwanie jest bardzo podobne do słownika, z wyjątkiem tego, że wiele wartości może być mapowanych na ten sam klucz, a klucze puste są obsługiwane.

Noble_Bright_Life
źródło
4

Jeśli wyjątek nie jest opcją, przejdź do Lookup

Jeśli próbujesz uzyskać strukturę tak wydajną jak a, Dictionaryale nie wiesz na pewno, że nie ma zduplikowanego klucza w danych wejściowych, Lookupjest bezpieczniejsze.

Jak wspomniano w innej odpowiedzi, obsługuje również klucze o wartości null i zwraca zawsze prawidłowy wynik podczas odpytywania z dowolnymi danymi, więc wydaje się być bardziej odporny na nieznane dane wejściowe (mniej podatny niż słownik na zgłaszanie wyjątków).

A jest to szczególnie prawdziwe, jeśli porównasz to z System.Linq.Enumerable.ToDictionaryfunkcją:

// won't throw
new[] { 1, 1 }.ToLookup(x => x); 

// System.ArgumentException: An item with the same key has already been added.
new[] { 1, 1 }.ToDictionary(x => x);

Alternatywą byłoby napisanie własnego zduplikowanego kodu zarządzania kluczami wewnątrz foreachpętli.

Uwagi dotyczące wydajności, słownik: wyraźny zwycięzca

Jeśli nie potrzebujesz listy i zamierzasz zarządzać ogromną liczbą elementów Dictionary(lub nawet własną niestandardową strukturą), byłoby bardziej wydajne:

        Stopwatch stopwatch = new Stopwatch();
        var list = new List<string>();
        for (int i = 0; i < 5000000; ++i)
        {
            list.Add(i.ToString());
        }
        stopwatch.Start();
        var lookup = list.ToLookup(x => x);
        stopwatch.Stop();
        Console.WriteLine("Creation: " + stopwatch.Elapsed);

        // ... Same but for ToDictionary
        var lookup = list.ToDictionary(x => x);
        // ...

Ponieważ Lookupmusi utrzymywać listę elementów dla każdego klucza, jest wolniejszy niż słownik (około 3x wolniejszy w przypadku dużej liczby elementów)

Szybkość wyszukiwania: tworzenie: 00: 00: 01.5760444

Prędkość słownika: tworzenie: 00: 00: 00.4418833

Fab
źródło