Dlaczego dict ma najgorszy przypadek O (n) w przypadku tak wielu operacji?

Question

Jak dokładnie zaimplementowano dict, że ma liniowe wyszukiwanie czasu na kolizje? Zakładam, że jest on zaimplementowany jako lista haseł wspierana przez listę. Zakładam, że lepszą implementacją będzie O (log (n)) dla różnych operacji, zamiast tego użyjemy drzewa, aby przywrócić tabelę. Czy za kulisami dzieje się jakaś magia, aby utrzymać ciągłe poszukiwania czasu przez jak najdłuższy czas?

Moje źródło to, nawiasem mówiąc, jest to:

http://www.google.com/search?sourceid=chrome&ie=UTF-8&q=python+complexity

Answer 1

Dict wynosi O (1) dla większości operacji, z wyjątkiem operacji, które dotykają wszystkich elementów, takich jak iteracji i kopii (w w tym przypadku jest to oczywiście O (n)).

Patrz: http://wiki.python.org/moin/TimeComplexity

Ma O (n) najgorszy przypadek, bo zawsze można wymyślić patologiczny przykład, w którym wszystkie klawisze mają tę samą wartość skrótu.

Answer 2

Weź pod uwagę nawet najlepszą funkcję skrótu w galaktyce. Nadal istnieje szansa, że ​​możesz podejść do jednego dnia z listą wartości, których najlepsza wartość funkcji mieszania jest taka sama. Jeśli umieścisz je w dyktowaniu, system nie ma innego wyjścia, jak tylko wykonywać liniowe wyszukiwania.

Stosowanie zbalansowanego drzewa utrzymywałoby najgorszy możliwy czas w punkcie O (log n), ale koszty utrzymania są dość wysokie. Zwykle tabele mieszania działają całkiem nieźle.

Answer 3

chciałbym przypuszczać, że lepsze wdrożenie byłoby O (log (n)) dla różnych operacji, wykorzystując drzewo zamiast kopii tabeli.

Tabele drzew i tabel mieszania mają bardzo różne wymagania i cechy wydajności.

• Drzewa wymagają zamówionego rodzaju.
• Drzewa wymagają porównywania zamówień, aby znaleźć obiekt. W przypadku niektórych obiektów, takich jak łańcuchy, zapobiega to niektórym znaczącym optymalizacjom: zawsze trzeba wykonać porównanie ciągów, które jest niedrogie. To sprawia, że ​​stały współczynnik O (log n) jest dość wysoki.
• Tabele skrótów wymagają typu skrótów i można testować równość, ale nie wymagają one typu uporządkowanego.
• Testy na równość można znacznie zoptymalizować. Jeśli internowane są dwa ciągi, możesz sprawdzić, czy są one równe w O (1), porównując ich wskaźnik, a nie O (n), porównując cały ciąg. Jest to optymalizacja masywna: w każdym wyszukiwaniu foo.bar, które zostanie przetłumaczone na foo.__dict__["bar"], "bar" jest internowanym ciągiem znaków.
• Tabele skrótu są w najgorszym przypadku O (n), ale sprawdzają, co prowadzi do najgorszego przypadku: bardzo kiepska implementacja tablicy mieszającej (np. Masz tylko jedną łyżkę) lub zepsuta funkcja skrótu, która zawsze zwraca to samo wartość. Kiedy masz odpowiednią funkcję mieszającą i odpowiedni algorytm fałszowania, wyszukiwania są bardzo tanie - bardzo często zbliżają się do stałego czasu.

Drzewa mają istotne zalety:

• Oni wydają się mieć mniejsze zapotrzebowanie na pamięć, ponieważ nie mają do przydzielenia wiadra.Najmniejsze drzewo może mieć 12 bajtów (wskaźnik węzłowy i dwa wskaźniki potomne), gdzie tablica skrótów ma zwykle 128 bajtów lub więcej - sys.getsizeof ({}) w moim systemie to 136.
• Umożliwiają one uporządkowane przemierzanie; niezwykle przydatna jest możliwość iteracji ponad [a, b) w uporządkowanym zestawie, którego tablice mieszania nie pozwalają.

ja uważam, że jest to wada, że ​​Python nie posiada standardowego drzewa binarnego pojemnik, ale dla charakterystyk wymaganych przez rdzeń Pythona, jak __dict__ wyszukiwań, stolik hash ma więcej sensu.

Answer 4

Punkt wyboru jednej implementacji na inną niekoniecznie dotyczy wartości upper-bound, ale raczej oczekiwanej wartości amortized performance. Podczas gdy różne algorytmy mogą mieć zdegenerowane przypadki, zwykle jest to "lepsze w praktyce" niż w przypadku podejścia z udowodnioną dolną górną granicą. W niektórych przypadkach jednak struktury muszą być zaprojektowane tak, aby chronić przed patologicznie złym wejściem.

Również niektóre języki/biblioteki - nie wiem o Pythonie - faktycznie zmieniają podstawową implementację, na przykład gdy liczba elementów przekracza n. Wpływa to na amortyzację wydajności (w niektórych przypadkach), ale niekoniecznie na big O.

Podsumowując: "to zależy".

Szczęśliwe kodowanie.

Answer 5

wiarygodnych źródeł informacji na temat funkcji hash i strategii kolizja rozdzielczości, które są faktycznie wykorzystanych zawierać komentarze w pliku źródłowym dictobject.c i całego pliku dictnotes.txt