Czy słowniki są zamawiane w Pythonie 3.6+?

Question

Słowniki są uporządkowane w Pythonie 3.6 (przynajmniej w wersji CPython) w przeciwieństwie do poprzednich wcieleń. Wydaje się to być istotną zmianą, ale jest to tylko krótki akapit w documentation. Jest on opisywany raczej jako detal implementacji CPython, a nie jako funkcja językowa, ale także sugeruje, że może to stać się standardem w przyszłości.

W jaki sposób implementacja nowego słownika działa lepiej niż starsza z zachowaniem kolejności elementów?

Oto tekst z dokumentacji:

dict() teraz używa „Compact” reprezentację pioneered by PyPy. Wykorzystanie pamięci nowego dicta() jest o 20% do 25% mniejsze w porównaniu z Pythonem 3.5. PEP 468 (Zachowanie kolejności ** kwargs w funkcji.) Jest realizowane przez to. Zachowujący porządek aspekt tej nowej implementacji jest uważany za szczegół implementacji i nie należy na niej polegać (może się to zmienić w przyszłości, ale pożądana jest nowa implementacja dyktowania w języku przez kilka wersji przed zmianą specyfikacji językowej aby zachować semantykę zachowującą porządek dla wszystkich obecnych i przyszłych implementacji Pythona, pomaga to również zachować kompatybilność wsteczną ze starszymi wersjami języka, w którym wciąż obowiązuje losowa kolejność iteracji, np. Python 3.5). (Autor Inada Naoki w issue 27350 pomysł originally suggested by Raymond Hettinger.).

Aktualizacja grudzień 2017: dict s zachowując kolejność wstawiania jest guaranteed Pythona 3,7

Answer 1

to słowniki zamówionej w Pythonie 3.6+?

są wstawiania uporządkowane^[1]. Od wersji Python 3.6, dla implementacji Pythona w CPython, słowniki pamiętają kolejność elementów wstawionych. Jest to uważane za szczegół implementacji w Pythonie 3.6; musisz użyć OrderedDict, jeśli chcesz zamówić zamawianie, które jest gwarantowane w innych implementacjach Pythona (i inne uporządkowane zachowanie ^[1]).

Od Pythona 3.7 nie jest to już szczegół implementacji i staje się funkcją językową. From a python-dev message by GvR:

Zrób tak. "Dict utrzymuje kolejność wstawiania" jest decyzją. Dzięki!

To po prostu oznacza, że ​​można na nim polegać . Inne implementacje Pythona muszą również zawierać słownik z poleceniem wstawiania, jeśli chcą być zgodną implementacją Pythona 3.7.

---

jaki sposób realizacja słownika Python 3.6 lepiej ^[2] niż starszy zachowując kolejność elementów?

Zasadniczo przez utrzymując dwie tablice.

• Pierwsza tablica, dk_entries, posiada pozycje (of type PyDictKeyEntry) dla słownika w kolejności ich zabezpieczenia. Zachowanie porządku osiąga się, gdy jest to tablica tylko do dodania, gdzie nowe elementy są zawsze wstawiane na końcu (kolejność wstawiania).

• Drugi dk_indices, posiada wskaźniki do tablicy dk_entries (to jest, wartości, które wskazują pozycję odpowiedniej pozycji w dk_entries). Ta tablica działa jako tablica asocjacyjna. Gdy klucz jest mieszany, prowadzi do jednego z indeksów zapisanych w dk_indices, a odpowiadający wpis jest pobierany przez indeksowanie dk_entries. Ponieważ tylko indeksy są przechowywane, rodzaj tej tablicy zależy od całkowitej wielkości słownika (od typu int8_t (1 bajtów) do int32_t/int64_t (4/8 bajtów) na 32/64 bit buduje)

W poprzedniej implementacji konieczne było przydzielenie rzadkiej tablicy typu PyDictKeyEntry i rozmiaru dk_size; niestety, spowodowało to również dużo pustej przestrzeni, ponieważ tablica ta nie mogła być większa niż 2/3 * dk_size pełna for performance reasons. (i pusta przestrzeń ma rozmiar).

ten nie jest obecnie ponieważ tylko wymagane zapisy są przechowywane (te, które zostały włożone) i rzadkie tablicą typu intX_t (X zależności od wielkości dict) 2/3 * dk_size pełnym jest utrzymywane.Pusta przestrzeń zmieniła się z typu PyDictKeyEntry na intX_t.

Oczywiście tworzenie rzadkiej tablicy typu PyDictKeyEntry wymaga o wiele więcej pamięci niż rzadka tablica do przechowywania int s.

Możesz zobaczyć pełną rozmowę na temat tej funkcji, jeśli jesteś zainteresowany, to jest dobra lektura.

---

In the original proposal made by Raymond Hettinger, wizualizacja struktur danych wykorzystywanych widać który oddaje istotę tego pomysłu.

Na przykład, Słownik:

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

jest obecnie przechowywane jako:

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

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

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

Jak możesz vi teraz widzimy, że w pierwotnej propozycji dużo miejsca jest w zasadzie puste, aby zmniejszyć liczbę kolizji i przyspieszyć wyszukiwanie. Dzięki nowemu podejściu zmniejszasz wymaganą pamięć, przesuwając rozrzedzenie tam, gdzie jest to naprawdę potrzebne, w indeksach.

---

_{[1]: powiedzieć „wstawiania uporządkowane”, a nie „uporządkowane”, ponieważ, z istnieniem OrderedDict „uporządkowane” sugeruje, że dalsze zachowanie dict Przedmiotem nie zapewnia. OrderedDicts są odwracalne, mają wrażliwe na zamówienia porównania i zapewniają metody wrażliwe na zamówienia. dict s obecnie nie oferują żadnego z tych zachowań/metod.}

---

_{[2] Nowe implementacje słownika wykonuje większą pamięci mądry będąc przeznaczony bardziej zwarty; to jest główna korzyść. Mądrość prędkości, różnica nie jest tak drastyczna, są miejsca, w których nowy dyktat może wprowadzać niewielkie regresje (key-lookups, for example), podczas gdy w innych (powtarzanie i zmiana rozmiaru) przychodzi do głowy.}

_{Ogólnie wydajność słownika, zwłaszcza w sytuacjach życiowych, poprawia ze względu na zwartość wprowadzone.}

Answer 2

Poniżej odpowiada pierwotnej pierwsze pytanie:

Czy powinienem używać dict lub OrderedDict w Pythonie 3.6?

Myślę, że to zdanie z dokumentacji jest faktycznie wystarczy odpowiedzieć na pytanie

Kolejność-konserwowanie aspekt tej nowej realizacji jest uważany szczegółów wdrażania i nie powinny być traktowane

dict nie jest wyraźnie przeznaczona do kolekcjonowania, więc jeśli chcesz zachować spójność i nie polegać na efektach ubocznych nowej implementacji, powinieneś pozostać przy OrderedDict.

Zrób swoją przyszłość kod dowód :)

Jest to debata o tym here.

EDIT: Python 3.7 będzie mieć to jako cechasee

Answer 3

Aktualizacja: Guido van Rossum announced on the mailing list że dicts we wszystkich implementacjach Python musi zachować kolejność wstawiania.