Wydajność słowników C #

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)

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.