Odpowiedzi:
Oto wszystko na temat słowników Python, które udało mi się zebrać (prawdopodobnie więcej niż ktokolwiek chciałby wiedzieć; ale odpowiedź jest wyczerpująca).
dictużywa otwartego adresowania do rozwiązywania kolizji mieszających (wyjaśnione poniżej) (patrz dictobject.c: 296-297 ).O(1)wyszukiwać według indeksu).Poniższy rysunek przedstawia logiczną reprezentację tabeli skrótów Pythona. Na poniższym rysunku 0, 1, ..., i, ...po lewej stronie znajdują się wskaźniki szczelin w tablicy skrótów (służą one wyłącznie celom ilustracyjnym i oczywiście nie są przechowywane razem ze stołem!).
# Logical model of Python Hash table
-+-----------------+
0| <hash|key|value>|
-+-----------------+
1| ... |
-+-----------------+
.| ... |
-+-----------------+
i| ... |
-+-----------------+
.| ... |
-+-----------------+
n| ... |
-+-----------------+Po zainicjowaniu nowego nagrania zaczyna się on od 8 miejsc . (patrz dictobject.h: 49 )
i, który jest oparty na skrócie klucza. CPython początkowo używa i = hash(key) & mask(gdzie mask = PyDictMINSIZE - 1, ale to nie jest tak naprawdę ważne). Pamiętaj tylko, że początkowy slot, iktóry jest sprawdzany, zależy od skrótu klucza.<hash|key|value>). Ale co, jeśli ten slot jest zajęty !? Najprawdopodobniej, ponieważ inny wpis ma ten sam skrót (kolizja skrótu!)==porównanie, a nie isporównanie) wpisu w gnieździe z skrótem i kluczem bieżącego wpisu do wstawienia ( dictobject.c : 337,344-345 ) odpowiednio. Jeśli oba pasują, oznacza to, że dany wpis już istnieje, poddaje się i przechodzi do następnego wpisu, który ma zostać wstawiony. Jeśli skrót lub klucz się nie zgadzają, zaczyna się sondowanie .i+1, i+2, ...i użyć pierwszego dostępnego (to jest sondowanie liniowe). Ale z powodów wyjaśnionych pięknie w komentarzach (patrz dictobject.c: 33-126 ), CPython używa losowego sondowania . W losowym badaniu kolejne miejsce jest wybierane w pseudolosowej kolejności. Wpis zostanie dodany do pierwszego pustego miejsca. W tej dyskusji faktyczny algorytm użyty do wybrania następnego gniazda nie jest tak naprawdę ważny (patrz algorytm sondowania na dictobject.c: 33-126 ). Ważne jest, aby gniazda były badane do momentu znalezienia pierwszego pustego gniazda.dictrozmiar zostanie zmieniony, jeśli jest zapełniony w dwóch trzecich. Pozwala to uniknąć spowolnienia wyszukiwania. (patrz dictobject.h: 64-65 )UWAGA: Przeprowadziłem badania dotyczące implementacji Python Dict w odpowiedzi na moje własne pytanie dotyczące tego, jak wiele wpisów w dykcie może mieć takie same wartości skrótu. Opublikowałem tutaj nieco zredagowaną wersję odpowiedzi, ponieważ wszystkie badania są również bardzo istotne dla tego pytania.
Jak wdrażane są słowniki wbudowane w Python?
Oto krótki kurs:
Uporządkowany aspekt jest nieoficjalny w Pythonie 3.6 (aby dać innym implementacjom szansę na dotrzymanie kroku), ale oficjalny w Pythonie 3.7 .
Przez długi czas działało dokładnie tak. Python wstępnie przydzieli 8 pustych wierszy i użyje skrótu, aby określić, gdzie należy przykleić parę klucz-wartość. Na przykład, jeśli skrót dla klucza zakończył się na 001, umieściłby go w indeksie 1 (tj. Drugim) (jak w przykładzie poniżej).
<hash> <key> <value>
null null null
...010001 ffeb678c 633241c4 # addresses of the keys and values
null null null
... ... ...Każdy wiersz zajmuje 24 bajty w architekturze 64-bitowej, 12 w 32-bitowej. (Pamiętaj, że nagłówki kolumn są tutaj tylko etykietami do naszych celów - tak naprawdę nie istnieją w pamięci).
Jeśli skrót zakończy się tak samo jak skrót istniejącego klucza, jest to kolizja, a następnie umieściłby parę klucz-wartość w innym miejscu.
Po zapisaniu 5 kluczy-wartości podczas dodawania kolejnej pary klucz-wartość prawdopodobieństwo kolizji skrótu jest zbyt duże, więc rozmiar słownika jest podwojony. W procesie 64-bitowym przed zmianą rozmiaru mamy 72 bajty puste, a następnie marnujemy 240 bajtów z powodu 10 pustych wierszy.
Zajmuje to dużo miejsca, ale czas wyszukiwania jest dość stały. Algorytm porównywania kluczy polega na obliczeniu wartości skrótu, przejściu do oczekiwanej lokalizacji, porównaniu identyfikatora klucza - jeśli są one tym samym obiektem, są równe. Jeśli nie, to porównanie wartości hash, jeśli są nie takie same, nie są one równe. W przeciwnym razie w końcu porównujemy klucze dla równości, a jeśli są równe, zwróć wartość. Ostateczne porównanie w zakresie równości może być dość powolne, ale wcześniejsze kontrole zwykle skracają końcowe porównanie, dzięki czemu wyszukiwanie jest bardzo szybkie.
Kolizje spowalniają działanie, a atakujący mógłby teoretycznie użyć kolizji mieszających, aby przeprowadzić atak typu „odmowa usługi”, więc losowo zainicjowaliśmy funkcję skrótu, tak aby obliczała różne wartości skrótu dla każdego nowego procesu Pythona.
Opisana powyżej zmarnowana przestrzeń doprowadziła nas do modyfikacji implementacji słowników, z nową ekscytującą funkcją, że słowniki są teraz porządkowane przez wstawienie.
Zamiast tego zaczynamy od wstępnego przydzielenia tablicy dla indeksu wstawienia.
Ponieważ nasza pierwsza para klucz-wartość znajduje się w drugim gnieździe, indeksujemy w następujący sposób:
[null, 0, null, null, null, null, null, null]A nasza tabela jest zapełniana według kolejności wstawiania:
<hash> <key> <value>
...010001 ffeb678c 633241c4
... ... ...Kiedy więc szukamy klucza, używamy skrótu, aby sprawdzić oczekiwaną pozycję (w tym przypadku przechodzimy prosto do indeksu 1 tablicy), a następnie przechodzimy do tego indeksu w tablicy skrótów (np. Indeks 0 ), sprawdź, czy klucze są równe (używając tego samego algorytmu opisanego wcześniej), a jeśli tak, zwróć wartość.
Zachowujemy stały czas wyszukiwania, z niewielkimi stratami prędkości w niektórych przypadkach i zyskami w innych, z zaletami, które oszczędzamy sporo miejsca w stosunku do wcześniejszej implementacji i zachowujemy kolejność wstawiania. Jedyne zmarnowane miejsce to puste bajty w tablicy indeksu.
Raymond Hettinger wprowadził to na Python-dev w grudniu 2012 roku. W końcu dostał się do CPython w Python 3.6 . Kolejność wstawiania była uważana za szczegół implementacji 3.6, aby umożliwić innym implementacjom Pythona szansę nadrobienia zaległości.
Kolejną optymalizacją w celu zaoszczędzenia miejsca jest implementacja dzieląca klucze. Dlatego zamiast redundantnych słowników, które zajmują całą tę przestrzeń, mamy słowniki, które ponownie wykorzystują wspólne klucze i skróty kluczy. Możesz myśleć o tym w ten sposób:
hash key dict_0 dict_1 dict_2...
...010001 ffeb678c 633241c4 fffad420 ...
... ... ... ... ...W przypadku komputera 64-bitowego może to zaoszczędzić do 16 bajtów na klucz na dodatkowy słownik.
Te dyktaje z kluczem wspólnym są przeznaczone do użycia w obiektach niestandardowych ” __dict__. Aby uzyskać takie zachowanie, uważam, że musisz zakończyć __dict__wypełnianie swojego pliku, zanim utworzysz kolejny obiekt ( patrz PEP 412 ). Oznacza to, że powinieneś przypisać wszystkie swoje atrybuty do __init__lub __new__, w przeciwnym razie możesz nie uzyskać oszczędności miejsca.
Jeśli jednak znasz wszystkie swoje atrybuty w momencie ich __init__wykonania, możesz również podać __slots__swój obiekt i zagwarantować, że __dict__w ogóle nie zostanie utworzony (jeśli nie jest dostępny w rodzicach), lub nawet pozwolić, __dict__ale zagwarantować, że twoje przewidywane atrybuty są i tak przechowywane w automatach. Aby uzyskać więcej informacji __slots__, zobacz moją odpowiedź tutaj .
**kwargsfunkcji.find_empty_slot: github.com/python/cpython/blob/master/Objects/dictobject.c # L969 - a od linii 134 jest proza, która to opisuje.
Słowniki Python używają otwartego adresowania ( odniesienie w pięknym kodzie )
NB! Otwartego adresowania , czyli zamkniętego haszowania, nie należy, jak zauważono w Wikipedii, nie mylić z jego przeciwstawnym otwartym haszowaniem!
Otwarte adresowanie oznacza, że dykt korzysta ze szczelin tablicowych, a gdy podstawowa pozycja obiektu jest przyjmowana w dyktonie, miejsce obiektu jest szukane pod innym indeksem w tej samej tablicy, przy użyciu schematu „perturbacji”, w którym wartość skrótu obiektu odgrywa rolę .