Jak wdrażane są słowniki wbudowane w Python?

Czy ktoś wie, jak zaimplementowano wbudowany słownik w Pythonie? Rozumiem, że jest to jakaś tabela haszująca, ale nie udało mi się znaleźć żadnej ostatecznej 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).

• Słowniki w języku Python są implementowane jako tabele skrótów .
• Tabele skrótów muszą zezwalać na kolizje skrótów, tzn. Nawet jeśli dwa odrębne klucze mają tę samą wartość skrótu, implementacja tabeli musi mieć strategię jednoznacznego wstawiania i pobierania par klucz i wartość.
• Python dictużywa otwartego adresowania do rozwiązywania kolizji mieszających (wyjaśnione poniżej) (patrz dictobject.c: 296-297 ).
• Tabela skrótów Pythona to tylko ciągły blok pamięci (coś w rodzaju tablicy, dzięki czemu można O(1)wyszukiwać według indeksu).
• Każde miejsce w tabeli może przechowywać jeden i tylko jeden wpis. To jest ważne.
• Każdy wpis w tabeli jest właściwie kombinacją trzech wartości: <skrót, klucz, wartość> . Jest to zaimplementowane jako struktura C (patrz dictobject.h: 51-56 ).

• 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 )

• Dodając wpisy do tabeli, zaczynamy od jakiegoś slotu 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.
• Jeśli ten slot jest pusty, wpis jest dodawany do slotu (przez wpis, mam na myśli, <hash|key|value>). Ale co, jeśli ten slot jest zajęty !? Najprawdopodobniej, ponieważ inny wpis ma ten sam skrót (kolizja skrótu!)
• Jeśli miejsce jest zajęte, CPython (a nawet PyPy) porównuje skrót ORAZ klucz (przez porównanie mam na myśli ==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 .
• Sondowanie oznacza po prostu, że przeszukuje gniazda według gniazda, aby znaleźć puste miejsce. Technicznie możemy po prostu przejść jeden po drugim 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.
• To samo dzieje się przy wyszukiwaniu, zaczyna się od początkowego gniazda i (gdzie i zależy od skrótu klawisza). Jeśli skrót i klucz nie pasują do wpisu w gnieździe, rozpoczyna sondowanie, aż znajdzie miejsce z pasującym dopasowaniem. Jeśli wszystkie gniazda są wyczerpane, zgłasza awarię.
• BTW, 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:

• Są to tabele skrótów. (Zobacz poniżej szczegóły implementacji Pythona).
• Nowy układ i algorytm, od wersji Python 3.6, czyni je
  • uporządkowane według klucza, oraz
  • zajmują mniej miejsca,
  • praktycznie bez kosztów wydajności.
• Kolejna optymalizacja oszczędza miejsce, gdy dyktaje klucze współdzielenia (w szczególnych przypadkach).

Uporządkowany aspekt jest nieoficjalny w Pythonie 3.6 (aby dać innym implementacjom szansę na dotrzymanie kroku), ale oficjalny w Pythonie 3.7 .

Słowniki Pythona to tabele skrótów

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.

Nowe kompaktowe tabele skrótów

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.

Klucze wspólne

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.

Wspólne klucze dla niestandardowych obiektów i alternatyw

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 .

Zobacz też:

• PEP 509 - Dodaj prywatną wersję do dyktowania
• PEP 468 - Zachowanie kolejności **kwargsfunkcji.
• PEP 520 - Zachowanie kolejności definicji atrybutów klas
• PyCon 2010: The Might Dictionary - Brandon Rhodes
• PyCon 2017: The Dictionary Even Mightier - Brandon Rhodes
• PyCon 2017: Nowoczesne słowniki Python Połączenie kilkunastu świetnych pomysłów - Raymond Hettinger
• dictobject.c - rzeczywista implementacja dict CPython w C.

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ę .