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.?

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.

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.

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.

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.

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.

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