Dlaczego Python używa tabeli skrótów do implementacji dict, ale nie czerwono-czarne drzewo? [Zamknięte]

Dlaczego Python używa tabeli skrótów do implementacji dict, ale nie czerwono-czarne drzewo?

Jaki jest klucz Występ?

Jest to ogólna odpowiedź niespecyficzna dla języka Python.

Porównanie złożoności algorytmicznej

       | Hash Table  |   Red-Black Tree    |
-------+-------------+---------------------+
Space  | O(n) : O(n) | O(n)     : O(n)     |
Insert | O(1) : O(n) | O(log n) : O(log n) |
Fetch  | O(1) : O(n) | O(log n) : O(log n) |
Delete | O(1) : O(n) | O(log n) : O(log n) |
       | avg  :worst | average  : worst    |

Problem z tabelami skrótów polega na tym, że skróty mogą się kolidować. Istnieją różne mechanizmy rozwiązywania kolizji, np. Otwarte adresowanie lub oddzielne tworzenie łańcuchów. Absolutnie najgorszym przypadkiem jest to, że wszystkie klucze mają ten sam kod skrótu, w którym to przypadku tabela skrótów ulegnie degradacji do połączonej listy.

We wszystkich innych przypadkach tablica skrótów jest świetną strukturą danych, łatwą do wdrożenia i zapewniającą dobrą wydajność. Minusem jest to, że implementacje, które mogą szybko powiększać tabelę i redystrybuować swoje wpisy, prawdopodobnie zmarnują prawie tyle pamięci, ile faktycznie jest używane.

Drzewa RB są samowyważące i w najgorszym przypadku nie zmieniają złożoności algorytmicznej. Są jednak trudniejsze do wdrożenia. Ich średnia złożoność jest również gorsza niż w przypadku tabeli skrótów.

Ograniczenia dotyczące kluczy

Wszystkie klucze w tabeli haszującej muszą być haszowalne i porównywalne, aby zapewnić sobie równość. Jest to szczególnie łatwe w przypadku ciągów lub liczb całkowitych, ale jest również dość łatwe do rozszerzenia na typy zdefiniowane przez użytkownika. W niektórych językach, takich jak Java, właściwości te są z definicji gwarantowane.

Klucze w drzewie RB muszą mieć całkowitą kolejność: każdy klucz musi być porównywalny z każdym innym kluczem, a oba klucze muszą albo porównywać mniejsze, większe lub równe. Ta równość porządkowa musi być równoważna z równością semantyczną. Jest to proste w przypadku liczb całkowitych i innych liczb, również dość łatwe w przypadku ciągów znaków (kolejność musi być tylko spójna i nie może być obserwowana z zewnątrz, więc kolejność nie musi uwzględniać ustawień narodowych ^[1] ), ale trudna w przypadku innych typów, które nie mają właściwej kolejności . Absolutnie niemożliwe jest posiadanie kluczy różnych typów, chyba że możliwe jest ich porównanie.

^{[1]: Właściwie tutaj się mylę. Dwa łańcuchy mogą nie być równe bajtom, ale nadal mogą być równoważne zgodnie z regułami niektórych języków. Zobacz np. Normalizacje Unicode dla jednego przykładu, w którym dwa równe łańcuchy są zakodowane inaczej. To, czy kompozycja znaków Unicode ma znaczenie dla klucza skrótu, jest czymś, czego implementacja tablicy skrótów nie może wiedzieć.}

Można by pomyśleć, że tanim rozwiązaniem dla kluczy RB-Tree byłoby najpierw sprawdzenie równości, a następnie porównanie tożsamości (tj. Porównanie wskaźników). Jednak ta kolejność nie byłaby przechodnia: jeśli a == bi id(a) > id(c), to również musi być zgodna z tym id(b) > id(c), co nie jest tutaj zagwarantowane. Zamiast tego możemy użyć kodu skrótu kluczy jako kluczy wyszukiwania. Tutaj porządkowanie działa poprawnie, ale możemy otrzymać wiele różnych kluczy z tym samym kodem skrótu, które zostaną przypisane do tego samego węzła w drzewie RB. Aby rozwiązać te kolizje skrótów, możemy zastosować oddzielne tworzenie łańcuchów, podobnie jak w przypadku tabel skrótów, ale dziedziczy to również najgorsze zachowanie dla tabel skrótów - najgorsze z obu światów.

Inne aspekty

• Oczekuję, że tablica skrótów będzie miała lepszą lokalizację pamięci niż drzewo, ponieważ tabela skrótów jest w zasadzie tylko tablicą.

• Wpisy w obu strukturach danych mają dość wysoki narzut:

  • tablica skrótów: klucz, wartość i wskaźnik następnego wpisu w przypadku oddzielnego tworzenia łańcuchów. Przechowywanie kodu skrótu może także przyspieszyć zmianę rozmiaru.
  • Drzewo RB: klucz, wartość, kolor, lewy wskaźnik potomny, prawy wskaźnik potomny. Zwróć uwagę, że chociaż kolor jest jednym bitem, problemy z wyrównaniem mogą oznaczać, że nadal będziesz marnował wystarczająco dużo miejsca na prawie cały wskaźnik, a nawet prawie cztery wskaźniki, gdy można przypisać tylko bloki pamięci o dwóch rozmiarach. W każdym razie pozycja drzewa RB zużywa więcej pamięci niż pozycja tabeli mieszania.

• Wstawienia i usunięcia w drzewie RB obejmują rotację drzewa. Nie są one naprawdę kosztowne, ale wiążą się z dodatkowymi kosztami. W skrócie wstawianie i usuwanie nie są droższe niż zwykły dostęp (chociaż zmiana rozmiaru tabeli skrótów po wstawieniu jest O(n)przedsięwzięciem).

• Tabele skrótów są z natury zmienne, podczas gdy drzewo RB można również wdrożyć w niezmienny sposób. Jest to jednak rzadko przydatne.

Istnieje wiele powodów, które mogą być prawdziwe, ale najważniejsze z nich to:

• Tabele skrótów są łatwiejsze do wdrożenia niż drzewa. Nie jest to całkowicie trywialne, ale tabele skrótów są nieco łatwiejsze, a wpływ na domenę legalnych kluczy jest mniej rygorystyczny, ponieważ potrzebujesz tylko funkcji skrótu i ​​funkcji równości; drzewa wymagają całkowitej funkcji zamówienia i jest to o wiele trudniejsze do napisania.
• Tabele skrótów (może) mają lepszą wydajność przy małych rozmiarach. Ma to duże znaczenie, ponieważ znaczna część pracy zajmuje się tylko teoretycznie dużymi zbiorami danych; w praktyce wiele z nich działa tylko z dziesiątkami lub setkami kluczy, a nie milionami. Wydajność na małą skalę ma duże znaczenie i nie można użyć analizy asymptotycznej, aby dowiedzieć się, co jest tam najlepsze; musisz faktycznie wdrożyć i zmierzyć.

Łatwiejsze pisanie / utrzymanie, a zwycięzca wydajności w typowych przypadkach użycia? Zarejestruj mnie, proszę!