Czy słowniki są uporządkowane w Pythonie 3.6+?

Czy słowniki są uporządkowane w Pythonie 3.6+?

Są wstawianie uporządkowane^[1]. Od wersji Python 3.6, dla implementacji Pythona CPython, słowniki zapamiętują kolejność wstawianych elementów . jest to uważane za szczegóły implementacji w Pythonie 3.6; musisz użyć OrderedDict, Jeśli chcesz, aby kolejność wstawiania była gwarantowana w innych implementacjach Pythona (i innych uporządkowanych zachowanie^[1]).

W Pythonie 3.7, nie jest to już szczegóły implementacji, a zamiast tego staje się cechą języka. from a python-dev message by GvR :

Niech tak będzie. "Dict utrzymuje porządek wstawiania" to orzeczenie. Dzięki!

Oznacza to po prostu, że możesz na tym polegać . Inne implementacje Pythona muszą również oferować wstawiony słownik, jeśli chcą być zgodne implementacja Pythona 3.7.

W Jaki Sposób implementacja słownika Pythona 3.6 działa lepiej^[2] niż starszy, zachowując porządek elementów?

Zasadniczo, przez utrzymanie dwóch tablic .

• Pierwsza tablica, dk_entries, przechowuje wpisy ( typu PyDictKeyEntry) do słownika w kolejności, w jakiej zostały wstawione. Zachowanie porządku uzyskuje się przez to, że jest to tylko dodatek tablica, gdzie nowe pozycje są zawsze wstawiane na końcu (kolejność wstawiania).

• Drugi, dk_indices, przechowuje indeksy dla tablicy dk_entries (to znaczy wartości, które wskazują pozycję odpowiedniego wpisu w dk_entries). Tablica ta działa jak tablica hash. Gdy klucz jest zahaszowany, prowadzi do jednego z indeksów przechowywanych w dk_indices, a odpowiadający mu wpis jest pobierany przez indeksowanie dk_entries. Ponieważ przechowywane są tylko indeksy, Typ tej tablicy zależy od ogólnej wielkości słownik (od typu int8_t(1 bajt) do int32_t/int64_t (4/8 bajtów) na 32/64 bit builds)

W poprzedniej implementacji trzeba było przydzielać nieliczną tablicę typu PyDictKeyEntry i rozmiaru dk_size; niestety, spowodowało to również dużo pustej przestrzeni, ponieważ ta tablica nie mogła być większa niż 2/3 * dk_size pełna ze względu na wydajność. (a pusta przestrzeń wciąż miała PyDictKeyEntry Rozmiar!).

Teraz tak nie jest, ponieważ tylko wymagane wpisy są przechowywane (te, które zostały wstawione) i rzadka tablica typu intX_t (X w zależności od wielkości dict) 2/3 * dk_sizejest zachowywana pełna. Pusta przestrzeń została zmieniona z typu PyDictKeyEntry na intX_t.

Możesz zobaczyć pełną rozmowę na Python-Dev dotyczącą tego funkcja jeśli zainteresowany, jest to dobra lektura.

W oryginalnej propozycji Raymonda Hettingera {63]} można zobaczyć wizualizację wykorzystanych struktur danych, która oddaje istotę idei.

Na przykład słownik:

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

Jest obecnie przechowywany jako:

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

Zamiast tego dane powinny być zorganizowane w następujący sposób:

indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]

Jak widać teraz wizualnie, w oryginalnej propozycji, dużo miejsca jest zasadniczo pusty, aby zmniejszyć kolizje i przyspieszyć wyszukiwanie. Dzięki nowemu podejściu zmniejszasz wymaganą pamięć, przesuwając skąpość tam, gdzie jest ona naprawdę wymagana, w indeksach.

_{[1]: mówię "wstawianie uporządkowane", a nie "uporządkowane", ponieważ, wraz z istnieniem OrderedDict," uporządkowane " sugeruje dalsze zachowanie, którego obiekt dict nie zapewnia. OrderedDicts są odwracalne, zapewniają metody wrażliwe na zamówienie i, głównie, zapewniają sensowne zamówienie testy równości (==, !=). dictS obecnie nie oferuje żadnego z tych zachowań / metod.}

_{[2]: nowa implementacja słownika działa lepiej Z pamięcią , ponieważ jest zaprojektowana bardziej kompaktowo; to jest główna korzyść tutaj. Jeśli chodzi o szybkość, różnica nie jest tak drastyczna, są miejsca, w których Nowy dict może wprowadzić niewielkie regresje (key-lookups, na przykład ), podczas gdy w innych (iteracja i zmiana rozmiaru przychodzą na myśl) wydajność boost powinien być obecny.}

_{Ogólnie rzecz biorąc, wydajność słownika, szczególnie w rzeczywistych sytuacjach, poprawia się ze względu na wprowadzoną zwartość.}