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 ContainsKey
metoda 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 dictionary
porównaniu ArrayList
zstructs(string,int)
źródło
Data Structures
ten link do wiki, który może ci pomócOdpowiedzi:
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”:
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?
Dla większości ludzi tabela skrótów jest tym, czego chcą.
Może się okazać, że SortedDictionary jest tym, czego chcesz:
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.
źródło