Wydajność słowników C #

14

Słowniki C # to prosty sposób na sprawdzenie, czy coś istnieje itp. Mam jednak pytanie, jak działają. Powiedzmy, że zamiast słownika używam ArrayList. Zamiast używać ContainsKey(lub równoważnej metody w innym języku) przeglądam ArrayList, aby sprawdzić, czy coś tam istnieje (lub przeprowadzam wyszukiwanie binarne, jeśli dane są sortowane lub coś podobnego). Jaka jest różnica w wydajności? Czy ContainsKeymetoda używa bardziej wydajnego sposobu niż zapętlanie kluczy i sprawdzenie, czy istnieje to, czego szukam?

Jeśli powiedzmy, że utworzyłem określoną funkcję skrótu, która odpowiada typowi danych, które posiadam i jest specjalnie zaprojektowana dla tego zestawu danych, to tak, ta funkcja skrótu jest rzeczywiście szybsza niż zapętlanie danych. Ale słowniki są ogólne. Metoda ContainsKey nie jest specyficzna dla danych, które otrzymuje, jest to ogólna metoda wyszukiwania.

Zasadniczo pytam o to. Słowniki są pomocne dla programistów. Obejmują metody, które pomagają w wielu rzeczach, łączą ciągi z liczbami całkowitymi (klucze i wartości) i wiele innych. Ale co do wydajności, co oferują? Jaka jest różnica w dictionaryporównaniu ArrayListzstructs(string,int)

John Demetriou
źródło
Naprawdę porównujesz tutaj jabłka do pomarańczy. Myślę, że słowem kluczowym, którego szukasz, jest Data Structures ten link do wiki, który może ci pomóc
Am

Odpowiedzi:

23

Musisz trochę wykopać, aby zobaczyć, jak słownik jest implementowany w C # - Nie jest to tak oczywiste, jak HashMap (tabela skrótów) lub TreeMap (posortowane drzewo) (lub ConcurrentSkipListMap - lista pominięć ).

Jeśli zagłębisz się w sekcję „Uwagi”:

Klasa ogólna Dictionary zapewnia mapowanie z zestawu kluczy na zestaw wartości. Każde dodanie do słownika składa się z wartości i związanego z nią klucza. Pobieranie wartości za pomocą jej klucza jest bardzo szybkie, zbliżone do O (1), ponieważ klasa Dictionary jest zaimplementowana jako tablica skrótów.

Mamy to. To jest tablica skrótów . Zauważ, że podłączyłem tam artykuł z Wikipedii - jest to dość dobra lektura. Możesz przeczytać sekcję dotyczącą rozwiązywania kolizji. Możliwe jest uzyskanie patologicznego zestawu danych, w którym wyszukiwanie przechodzi do O (N) (na przykład wszystko, co wstawisz, spada z tej samej wartości skrótu lub indeksu w tabeli skrótów z jakiegoś powodu i pozostaje ci liniowe sondowanie ).

Chociaż Słownik jest rozwiązaniem ogólnego zastosowania, nie powinieneś omijać konkretnych typów (takich jak Słownik) - powinieneś omijać interfejsy. W tym przypadku jest to interfejs IDictionary( docs ). W tym celu jesteś w stanie napisać własną implementację słownika, która optymalnie dostosowuje się do posiadanych danych.

Co do skuteczności różnych wyszukiwania / zawiera?

  • Zwiedzanie nieposortowanej listy: O (N)
  • Wyszukiwanie binarne posortowanej tablicy: O (log N)
  • Posortowane drzewo: O (log N)
  • Tabela skrótów: O (1)

Dla większości ludzi tabela skrótów jest tym, czego chcą.

Może się okazać, że SortedDictionary jest tym, czego chcesz:

SortedDictionary<TKey, TValue>Klasa rodzajowy jest wyszukiwanie binarne drzewo z O (log n) pobierania, gdzie n jest liczbą elementów w słowniku. Pod tym względem jest podobny do SortedList<TKey, TValue>klasy ogólnej. Dwie klasy mają podobne modele obiektowe i obie mają pobieranie O (log n).

Chociaż znowu, jeśli struktura danych nie jest idealna dla twoich danych, masz narzędzia (interfejsy), aby móc napisać takie, które najlepiej pasują do twoich danych.

Sam słownik jest abstrakcyjnym typem danych . Dajesz mi Słownik, a ja wiem, co mogę z tym zrobić i wszystkie dostępne tam narzędzia, których mogę używać, ponieważ jest to Słownik. Gdybyś podał mi ArrayList, pisałbym własny kod do wyszukiwania, wstawiania lub usuwania elementów z listy. To marnuje mój czas, a także oznacza, że ​​istnieje większe prawdopodobieństwo błędu, ponieważ kopiuję kod raz po raz z miejsca na miejsce.

Robert Harvey
źródło
5
O (1) niekoniecznie jest „szybki”. Pętlowanie listy może być szybsze niż tablica skrótów dla rozmiarów kolekcji, z którymi ma do czynienia aplikacja.
whatsisname
5
@whatsisname w żadnym momencie nie twierdzę, że O (1) jest szybki. Z pewnością może być najszybszy. Iteracja po kluczach tablicy hashtable jest wolniejsza niż w ArrayList (chyba że używasz czegoś takiego jak LinkedHashMap, który zapewnia Java). Ważne jest, aby znać swoje dane i ich zachowanie oraz wybrać odpowiednią dla nich kolekcję - a jeśli to nie istnieje, napisz ją. Zakładając oczywiście, że takie przedsięwzięcie jest rzeczywiście warte czasu (najpierw profil!).
W cytacie jest napisane: „Pobieranie wartości za pomocą jej klucza jest bardzo szybkie, zbliżone do O (1), ponieważ klasa Dictionary jest zaimplementowana jako tablica skrótów.”, Więc OP może pomylić te dwie koncepcje. Innymi słowy, chciałem wyjaśnić, że duże O nie opowiada całej historii dotyczącej „prędkości”.
whatsisname
3
@whatsisname, która jest bezpośrednio od Microsoft. Użycie klucza do wyszukania wartości, chyba że masz patologiczny zbiór skrótów (który rozwiązuje kolizje skrótu z innym mechanizmem) będzie szybszy niż wyszukiwanie go w drzewie lub posortowanej liście (lub nieposortowanej liście). Na przykład Java używa sondowania liniowego (krok 1) do rozwiązywania kolizji - co może być wolniejsze w przypadkach, gdy tabela jest zbyt pełna lub zderza się zbyt wiele skrótów. W ogólnym przypadku jest jednak wystarczająco dobry.
Jako odpowiedni przykład niedawno zoptymalizowałem trochę kodu w c ++, który pierwotnie używał tabeli skrótów dla zestawów danych około 20 wpisów i jej ukończenie zajęło około 400 ms. Przejście na drzewo binarne obniżyło to do 200 ms, ponieważ dostęp do drzewa jest łatwiejszy. Ale udało mi się to jeszcze bardziej ograniczyć, używając tablicy par nazw wartości i heurystycznej funkcji wyszukiwania, która zgadła, od czego zacząć szukać na podstawie wcześniejszych wzorców dostępu. Więc wszystko zależy od tego, ile danych jest i jakie są wzorce w dostępach (np. Lokalizacja).
Jules