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

Słowniki są uporządkowane w Pythonie 3.6 (przynajmniej w ramach implementacji CPython), inaczej niż w poprzednich wcieleniach. To wydaje się być istotną zmianą, ale jest to tylko krótki akapit w dokumentacji . Jest opisywany jako szczegół implementacji CPython, a nie jako funkcja językowa, ale sugeruje również, że może stać się standardem w przyszłości.

W jaki sposób nowa implementacja słownika działa lepiej niż starsza przy zachowaniu kolejności elementów?

Oto tekst z dokumentacji:

dict()wykorzystuje teraz „kompaktową” reprezentację zapoczątkowaną przez PyPy . Zużycie pamięci nowego dict () jest od 20% do 25% mniejsze w porównaniu do Pythona 3.5. PEP 468 (Zachowanie kolejności ** kwargs w funkcji.) Jest przez to realizowane. Aspekt zachowywania porządku w tej nowej implementacji jest uważany za szczegół implementacji i nie należy na nim polegać (może się to zmienić w przyszłości, ale pożądane jest, aby ta nowa implementacja dict w języku była dostępna przez kilka wydań przed zmianą specyfikacji języka narzucenie semantyki zachowującej porządek dla wszystkich bieżących i przyszłych implementacji Pythona; pomaga to również zachować zgodność wsteczną ze starszymi wersjami języka, w którym wciąż obowiązuje kolejność losowych iteracji, np. Python 3.5). (Wkład INADA Naoki wwydanie 27350 . Pomysł pierwotnie zasugerowany przez Raymonda Hettingera .)

Aktualizacja z grudnia 2017 r .: w Pythonie 3.7 gwarantowanadict jest zachowana kolejność wstawiania

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

Są one wstawiane ^[1] . Począwszy od Pythona 3.6, w implementacji CPython w Pythonie słowniki zapamiętują kolejność wstawianych elementów . Jest to uważane za szczegół implementacji w Pythonie 3.6 ; musisz użyć, OrderedDictjeśli chcesz porządkować wstawianie, które jest gwarantowane w innych implementacjach Pythona (i innych uporządkowanych zachowaniach ^[1] ).

Od wersji Python 3.7 nie jest to już szczegół implementacji, a zamiast tego staje się funkcją języka. Z wiadomości napisanej przez GvR w python-dev :

Zrób to tak. „Dict utrzymuje kolejność wstawiania” to orzeczenie. Dzięki!

Oznacza to po prostu, że możesz na tym polegać . Inne implementacje Pythona muszą także oferować słownik z wstawionym słownikiem, jeśli chcą być zgodną implementacją Pythona 3.7.

W jaki sposób 3.6implementacja słownika Python działa lepiej ^[2] niż starsza, zachowując kolejność elementów?

Zasadniczo poprzez utrzymanie dwóch tablic .

• Pierwsza tablica dk_entrieszawiera wpisy ( typuPyDictKeyEntry ) słownika w kolejności ich wstawienia. Porządek zachowania jest osiągany przez to, że jest to tablica tylko do dołączania, w której nowe elementy są zawsze wstawiane na końcu (kolejność wstawiania).

• Drugi, dk_indiceszawiera wskaźniki dla dk_entriestablicy (czyli wartości wskazujące pozycję odpowiedniego wpisu w dk_entries). Ta tablica działa jak tablica skrótów. Gdy klucz jest mieszany, prowadzi on do jednego z przechowywanych indeksów, dk_indicesa odpowiedni wpis jest pobierany przez indeksowanie dk_entries. Ponieważ przechowywane są tylko indeksy, typ tej tablicy zależy od ogólnego rozmiaru słownika (od typu int8_t( 1bajt) do int32_t/ int64_t( 4/ 8bajty) w 32/ 64kompilacjach bitowych)

W poprzedniej implementacji konieczne było przydzielenie rzadkiej tablicy typu PyDictKeyEntryi rozmiaru dk_size; Niestety, to również spowodowało dużo pustej przestrzeni ponieważ tablica nie wolno było mieć więcej niż 2/3 * dk_sizepełny ze względu na wydajność . (a puste miejsce wciąż miało PyDictKeyEntryrozmiar!).

Teraz tak nie jest, ponieważ przechowywane są tylko wymagane wpisy (te, które zostały wstawione) i zachowana jest rzadka tablica typu intX_t(w Xzależności od rozmiaru nagrania) 2/3 * dk_sizepełna. Puste miejsce zmieniło się z typu PyDictKeyEntryna intX_t.

Tak więc, oczywiście, tworzenie rzadkiej tablicy typu PyDictKeyEntrywymaga znacznie więcej pamięci niż rzadka tablica do przechowywania ints.

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

W oryginalnej propozycji Raymonda Hettingera można zobaczyć wizualizację zastosowanych struktur danych, która oddaje sedno tego pomysłu.

Na przykład słownik:

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

jest obecnie przechowywany jako [skrót, klucz, wartość]:

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

Zamiast tego dane należy uporządkować 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, w oryginalnej propozycji dużo miejsca jest zasadniczo puste, aby zmniejszyć kolizje i przyspieszyć wyszukiwanie. Dzięki nowemu podejściu zmniejszasz wymaganą pamięć, przesuwając rzadkość tam, gdzie jest naprawdę wymagana, w indeksach.

_{[1]: Mówię „wstawione uporządkowane”, a nie „uporządkowane”, ponieważ przy istnieniu OragedDict „uporządkowane” sugeruje dalsze zachowanie, którego dictobiekt nie zapewnia . OrdersDicts są odwracalne, zapewniają metody uwzględniające porządek, a przede wszystkim zapewniają testy równości uwzględniające porządek ( ==, !=). dictObecnie nie oferują żadnego z tych zachowań / metod.}

_{[2]: Nowe implementacje słownika mają lepszą pamięć, ponieważ są bardziej zwarte; to główna zaleta tutaj. Jeśli chodzi o szybkość, różnica nie jest tak drastyczna, są miejsca, w których nowy dyktat może wprowadzić niewielkie regresje ( na przykład wyszukiwanie kluczowych kluczy ), podczas gdy w innych (przychodzą na myśl iteracja i zmiana rozmiaru) powinno być obecne zwiększenie wydajności.}

_{Ogólnie, wydajność słownika, szczególnie w rzeczywistych sytuacjach, poprawia się dzięki wprowadzonej zwartości.}

Poniżej znajduje się odpowiedź na pierwsze pytanie:

Czy powinienem używać dictczy OrderedDictw Pythonie 3.6?

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

Aspekt utrzymywania porządku w tej nowej implementacji jest uważany za szczegół implementacji i nie należy na nim polegać

dictnie jest wyraźnie przeznaczona do kolekcji uporządkowanej, więc jeśli chcesz zachować spójność i nie polegać na skutkach ubocznych nowej implementacji, powinieneś się jej trzymać OrderedDict.

Niech Twój kod będzie przyszłościowy :)

Jest to debata o tym tutaj .

EDYCJA: Python 3.7 zachowa to jako funkcję zobacz

Aktualizacja: Guido van Rossum ogłosił na liście mailowej, że począwszy od Pythona 3.7 dicts we wszystkich implementacjach Pythona musi zachowywać kolejność wstawiania.

Chciałem dodać do powyższej dyskusji, ale nie mam reputacji do komentowania.

Python 3.8 nie został jeszcze wydany, ale będzie nawet zawierać reversed()funkcję w słownikach (usuwając kolejną różnicę OrderedDict.

Dict i dictviews są teraz iterowalne w odwróconej kolejności wstawiania za pomocą reverse (). (Autor: Rémi Lapeyre w bpo-33462.) Zobacz, co nowego w python 3.8

Nie widzę żadnej wzmianki o operatorze równości ani innych cechach, OrderedDictwięc wciąż nie są one do końca takie same.