Drzewa binarne a listy połączone a tabele Hash

Stosuje się standardowe kompromisy między tymi strukturami danych.

• Drzewa Binarne
  • średnia złożoność do zaimplementowania (zakładając, że nie możesz pobrać ich z biblioteki)
  • wstawki są O(logN)
  • lookups are O(logN)
• Linked lists (unsorted)
  • Mała złożoność implementacji
  • wstawki są O(1)
  • lookups are O(N)
• tabele Hash
  • duża złożoność implementacji
  • wstawki są O (1) na średnia
  • lookups are O(1) on average

Wydaje się, że wszyscy zapominają, że dla małych Ns, czyli kilku symboli w tabeli, lista połączona może być znacznie szybsza niż tabela hash, chociaż teoretycznie jej asymptotyczna złożoność jest rzeczywiście wyższa.

Jest słynny qoute z notatek Pike 'a na temat programowania w C:" reguła 3. Wymyślne algorytmy są powolne, gdy n jest małe, a n jest zwykle małe. Wymyślne algorytmy mają duże stałe. Dopóki nie wiesz, że n jest często będzie duży, nie daj się fantazji." http://www.lysator.liu.se/c/pikestyle.html

Nie mogę stwierdzić z twojego postu, czy będziesz miał do czynienia z małym N, czy nie, ale zawsze pamiętaj, że najlepszy algorytm dla dużych N niekoniecznie jest dobry dla małych N.

Wygląda na to, że wszystko może być prawdą:

Twoje klucze to sznurki.
• wstawki są wykonywane raz.
• wyszukiwanie odbywa się często.
• liczba par klucz-wartość jest stosunkowo mała (powiedzmy, mniej niż K lub tak).

Jeśli tak, możesz rozważyć posortowanie listy nad którąkolwiek z tych innych struktur. Byłoby to gorsze niż inne podczas wstawiania, ponieważ posortowana lista to O (N) na wstawianiu, w porównaniu z O(1) dla listy połączonej lub tabeli hash, oraz O (log₂N) dla zbalansowanego drzewa binarnego. Ale wyszukiwanie na posortowanej liście może być szybsze niż którekolwiek z tych innych struktur (wyjaśnię to wkrótce), więc możesz wyjść na górę. Ponadto, jeśli wykonasz wszystkie swoje wstawki naraz(lub w inny sposób nie wymagasz wyszukiwania, dopóki wszystkie wstawki nie zostaną zakończone), możesz uprościć wstawki do O (1) i zrobić jedno znacznie szybsze sortowanie na końcu. Co więcej, posortowana lista zużywa mniej pamięci niż jakakolwiek z tych innych struktur, ale jedynym sposobem jest prawdopodobnie ma znaczenie, jeśli masz wiele małych list. Jeśli masz jedną lub kilka dużych list, tabela skrótów prawdopodobnie wykona listę posortowaną.

Dlaczego wyszukiwanie może być szybsze z posortowaną listą? Cóż, jasne jest, że jest szybszy niż lista połączona, z czasem wyszukiwania O(N) tej drugiej. Z binarnym drzewem, lookupy pozostają tylko O (log₂ N) jeśli drzewo pozostaje idealnie zrównoważone. Utrzymanie równowagi drzewa (na przykład czerwony-czarny) zwiększa złożoność i czas wstawiania. Dodatkowo, zarówno z listami linkowanymi, jak i drzewami binarnymi, każdy element jest odrębnie przydzielany¹node , co oznacza, że będziesz musiał dereferować wskaźniki i prawdopodobnie przeskoczyć do potencjalnie bardzo różnych adresów pamięci, zwiększając szanse na brak pamięci podręcznej.

Jeśli chodzi o tabele hashowe, powinieneś przeczytać kilka z innych pytań tutaj na StackOverflow, ale główne punkty zainteresowania to:

• tabela hash może zdegenerować się do O (N) w najgorszym przypadku.
• koszt hashowania jest niezerowy, a w niektórych implementacjach może być znaczący, szczególnie w przypadku łańcuchów.
• podobnie jak w linkowanych listach i drzewach binarnych, każdy wpis jest węzłem przechowującym więcej niż tylko klucz i wartość, również oddzielnie-przydzielonym w niektórych implementacjach, więc zużywasz więcej pamięci i zwiększasz szanse na brak pamięci podręcznej.

Oczywiście, jeśli naprawdę zależy ci na tym, jak któreś z tych struktur danych będzie działać, powinieneś przetestuj je. Powinieneś mieć mały problem ze znalezieniem dobrych implementacji któregokolwiek z nich dla większości popularnych języków. Nie powinno być zbyt trudne rzucanie niektórych rzeczywistych danych na każdą z tych struktur danych i sprawdzanie, która z nich działa najlepiej.

1. _{implementacja może wstępnie przydzielić tablicę węzłów, co pomogłoby w problemie z pominięciem pamięci podręcznej. Nie widziałem tego w żadnej prawdziwej implementacji linkowanych list lub binarnych drzew (nie żebym widział każdą z nich, z oczywiście), choć na pewno można by toczyć własne. Nadal jednak istnieje nieco większa możliwość pominięcia pamięci podręcznej, ponieważ obiekty węzeł byłyby koniecznie większe niż pary klucz/wartość.}

Podoba mi się odpowiedź Billa, ale to nie do końca syntetyzuje rzeczy.

Z trzech opcji:

Listy połączone są stosunkowo powolne do wyszukiwania elementów z (O (n)). Więc jeśli masz dużo przedmiotów w tabeli, lub masz zamiar robić wiele Wyszukiwania, to nie są najlepszym wyborem. Są jednak łatwe do zbudowania i łatwe do napisania. Jeśli tabela jest mała i / lub wykonujesz tylko jedno małe skanowanie po jej zbudowaniu, może to być wybór dla ty.

Tabele Hash mogą być niesamowicie szybkie. Jednak, aby to zadziałało, musisz wybrać dobry hash dla swojego wejścia i musisz wybrać tabelę wystarczająco dużą, aby pomieścić wszystko bez wielu kolizji hash. Oznacza to, że musisz wiedzieć coś o wielkości i ilości swojego wkładu. Jeśli to zepsujesz, skończysz z naprawdę drogim i złożonym zestawem połączonych list. Powiedziałbym, że jeśli nie wiesz wcześniej z grubsza, jak duży stół będzie, nie używaj hash stolik. Nie zgadza się to z Twoją "zaakceptowaną" odpowiedzią. Przepraszam.

To pozostawia drzewa. Masz tu jednak opcję: zrównoważyć lub nie zrównoważyć. Co znalazłem badając ten problem na C i Fortran kod mamy tutaj jest to, że wprowadzanie tabeli symboli wydaje się być wystarczająco losowe, że tracisz tylko o poziom drzewa lub dwa nie równoważenia drzewa. Biorąc pod uwagę, że zrównoważone drzewa są wolniejsze do wstawiania elementów i są trudniejsze do wdrożenia, nie zawracałbym sobie nimi głowy. Jednakże, jeśli masz już dostęp do debugowanych bibliotek komponentów nice (np.: STL C++), więc równie dobrze możesz użyć zbalansowanego drzewa.

Kilka rzeczy na które warto uważać.

• Drzewa binarne mają tylko o (log n) lookup i insert złożoność, jeśli drzewo jest zrównoważone . Jeśli Twoje symbole są wstawiane w dość przypadkowy sposób, nie powinno to stanowić problemu. Jeśli zostaną wstawione w kolejności, utworzysz połączoną listę. (Dla konkretnego zastosowania nie powinny być w żadnej kolejności, więc powinieneś być w porządku.) Jeśli jest szansa, że symbole będą zbyt uporządkowane, Czerwono-Czarne drzewo jest lepsze rozwiązanie.

• Tabele Hash dają o (1) średnią złożoność wstawiania i wyszukiwania, ale tu też jest zastrzeżenie. Jeśli twoja funkcja hash jest zła (i mam na myśli naprawdę źle), możesz również zbudować linkowaną listę tutaj. Każda rozsądna funkcja hash string powinna to zrobić, więc to Ostrzeżenie jest tak naprawdę tylko po to, aby upewnić się, że jesteś świadomy, że może się zdarzyć. Powinieneś być w stanie sprawdzić, czy twoja funkcja hash nie ma wielu kolizji w oczekiwanym zakresie wejść i będzie dobrze. Inną drobną wadą jest użycie tabeli hash o stałym rozmiarze. Większość implementacji tabel hashowych rośnie, gdy osiągną określony rozmiar(współczynnik obciążenia, aby być bardziej precyzyjnym, zobacz tutaj Po szczegóły). Ma to na celu uniknięcie problemu, który pojawia się, gdy wkładasz milion symboli do dziesięciu wiader. To tylko prowadzi do dziesięciu połączonych list o średniej wielkości 100,000.

• Użyłbym tylko połączonej listy, gdybym miał naprawdę krótką tabelę symboli. On najłatwiejsza do wdrożenia, ale najlepsza wydajność dla połączonej listy jest najgorszą wydajnością dla pozostałych dwóch opcji.

Inne komentarze skupiły się na dodawaniu/pobieraniu elementów, ale ta dyskusja nie jest kompletna bez rozważenia, co trzeba zrobić, aby iterację nad całą kolekcją. Krótka odpowiedź jest taka, że tabele hash wymagają mniej pamięci do iteracji, ale drzewa wymagają mniej czasu.

Dla tabeli hash, obciążenie pamięci iteracji przez pary (klucz, wartość) nie zależy od pojemności tabeli ani od liczby elementów przechowywanych w tabeli; w rzeczywistości iteracja powinna wymagać tylko jedna zmienna indeksu lub dwie.

Dla drzew wymagana ilość pamięci zawsze zależy od wielkości drzewa. Możesz albo utrzymywać kolejkę niezauważonych węzłów podczas iteracji, albo dodawać dodatkowe wskaźniki do drzewa dla łatwiejszej iteracji( sprawiając, że drzewo, do celów iteracji, działa jak lista połączona), ale tak czy inaczej, musisz przeznaczyć dodatkową pamięć do iteracji.

Ale sytuacja jest odwrotna, jeśli chodzi o czas. Dla tabeli hash, czas potrzebny do iteracja zależy od pojemności tabeli, a nie od ilości przechowywanych elementów. Więc tabela załadowana na 10% pojemności zajmie około 10 razy więcej czasu niż lista połączona z tymi samymi elementami!

To oczywiście zależy od kilku rzeczy. Powiedziałbym, że lista połączona jest od razu, ponieważ ma kilka odpowiednich właściwości do pracy jako tabela symboli. Drzewo binarne może działać, jeśli już je posiadasz i nie musisz tracić czasu na pisanie i debugowanie. Moim wyborem byłaby tabela hash, myślę, że jest to mniej więcej domyślna dla tego celu.

To pytanie przechodzi przez różne kontenery w C#, ale są one podobne w każdym języku, którego używasz.

Jeśli nie oczekujesz, że Twoja tabela symboli będzie mała, powinienem trzymać się z dala od połączonych list. Lista 1000 przedmiotów zajmie średnio 500 iteracji, aby znaleźć dowolny przedmiot w niej.

Drzewo binarne może być znacznie szybsze, o ile jest zrównoważone. Jeśli nadal utrzymujesz zawartość, serializowana forma prawdopodobnie zostanie posortowana, a po ponownym załadowaniu wynikowe drzewo będzie w konsekwencji całkowicie niezrównoważone i będzie zachowywać się tak samo, jak lista połączona - ponieważ w zasadzie tak to wygląda stało się. Algorytmy Balanced tree rozwiązują tę sprawę, ale sprawiają, że całość jest bardziej złożona.

Haszmapa (o ile wybierzesz odpowiedni algorytm haszujący) wygląda na najlepsze rozwiązanie. Nie wspomniałeś o swoim środowisku, ale prawie wszystkie współczesne języki mają wbudowaną Hashmapę.