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

467

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

Chris_Rands
źródło
2
Zobacz ten wątek na liście mailingowej Python-Dev: mail.python.org/pipermail/python-dev/2016-September/146327.html, jeśli go nie widziałeś; jest to po prostu dyskusja na te tematy.
mgc
1
Jeśli kwargs mają być teraz zamawiane (co jest fajnym pomysłem), a kwargs to dict, a nie OrdersDict, to przypuszczam, że można założyć, że klucze dict pozostaną zamówione w przyszłej wersji Pythona, mimo że dokumentacja mówi inaczej.
Dmitriy Sintsov
4
@DmitriySintsov Nie, nie zakładaj tego. Był to problem poruszony podczas pisania PEP, który definiuje funkcję zachowania porządku **kwargsi jako takie użyte sformułowanie jest dyplomatyczne: **kwargsw funkcji podpis jest teraz gwarantowany jako mapowanie zachowujące porządek wstawiania . Użyli terminu mapowanie , aby nie zmuszać innych implementacji do nakazania dyktowania (i użycia OrderedDictwewnętrznego) oraz jako sposób zasygnalizowania, że ​​nie powinno to zależeć od faktu, że dictnie jest ono uporządkowane.
Dimitris Fasarakis Hilliard
7
Dobre wyjaśnienie wideo od Raymonda Hettingera
Alexa
1
@wazoox, kolejność i złożoność mapy skrótów nie uległa zmianie. Zmiana powoduje zmniejszenie wartości skrótu poprzez marnowanie mniejszej ilości miejsca, a zaoszczędzone miejsce jest (zwykle?) Większe niż zajmuje tablica pomocnicza. Szybciej, mniej, zamówiłem - musisz wybrać wszystkie 3.
John La Rooy

Odpowiedzi:

510

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.

Dimitris Fasarakis Hilliard
źródło
15
Co się stanie, gdy element zostanie usunięty? czy entrieszmieniono rozmiar listy? czy jest zachowane puste miejsce? czy od czasu do czasu jest kompresowany?
njzk2
18
@ njzk2 Kiedy element jest usuwany, odpowiedni indeks jest zastępowany przez DKIX_DUMMYwartość -2i wpis w entrytablicy zastępowany przezNULL , gdy wstawianie jest wykonywane, nowe wartości są dodawane do tablicy wpisów, Nie byłem jeszcze w stanie rozpoznać, ale jest całkiem pewne, że gdy indeksy wypełnią się powyżej 2/3progu, zostanie przeprowadzona zmiana rozmiaru. Może to prowadzić do zmniejszania się zamiast wzrostu, jeśli DUMMYistnieje wiele wpisów.
Dimitris Fasarakis Hilliard
3
@Chris_Rands Nie, jedyną faktyczną regresją, którą widziałem, jest śledzenie w wiadomości od Victora . Poza tym mikrodrukiem nie widziałem żadnego innego problemu / komunikatu wskazującego na poważną różnicę prędkości w rzeczywistych obciążeniach roboczych. Są miejsca, w których nowy dyktand może wprowadzać niewielkie regresje (na przykład wyszukiwania kluczy), podczas gdy w innych (przychodzą na myśl iteracja i zmiana rozmiaru) może wystąpić wzrost wydajności.
Dimitris Fasarakis Hilliard
3
Korekta w części dotyczącej zmiany rozmiaru : Słowniki nie zmieniają rozmiaru po usunięciu elementów, ponownie obliczają po ponownym wstawieniu. Jeśli więc utworzysz dykt, d = {i:i for i in range(100)}a .popwszystkie elementy nie zostaną wstawione, rozmiar się nie zmieni. Po ponownym dodaniu d[1] = 1obliczany jest odpowiedni rozmiar i zmienia rozmiar dykta.
Dimitris Fasarakis Hilliard
6
@Chris_Rands Jestem prawie pewien, że zostanie. Chodzi o to, a powodem, dla którego zmieniłem odpowiedź, aby usunąć ogólne stwierdzenia o „ dictbyciu zamówionym”, dictnie są uporządkowane w tym sensie, OrderedDictże są. Ważną kwestią jest równość. dictmają niewrażliwe na porządek ==, OrderedDictmają wrażliwe na porządek. Zrzuty OrderedDicti zmiana dictsna teraz z porównaniami wrażliwymi na porządek mogą prowadzić do wielu uszkodzeń starego kodu. Domyślam się, że jedyną rzeczą, która może się zmienić w OrderedDicts, jest jego implementacja.
Dimitris Fasarakis Hilliard
66

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

Maresh
źródło
1
Wydaje się, że jeśli nie mieli na myśli, że jest to prawdziwa funkcja, a jedynie szczegół implementacji, to nie powinni nawet umieszczać jej w dokumentacji.
xji,
3
Nie jestem pewien co do twojego zastrzeżenia dotyczącego edycji; ponieważ gwarancja dotyczy tylko Pythona 3.7, zakładam, że porada dla Pythona 3.6 pozostaje niezmieniona, tzn. dyktaty są zamawiane w CPython, ale nie licz na to
Chris_Rands
25

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.

fjsj
źródło
2
Teraz, gdy porządkowanie kluczy jest oficjalnym standardem, jaki jest cel OragedDict? Czy jest teraz zbędny?
Jonny Waffles
2
Wydaje mi się, że OrdersDict nie będzie zbędny, ponieważ ma move_to_endmetodę, a jej równość jest wrażliwa na kolejność: docs.python.org/3/library/… . Zobacz notatkę na temat odpowiedzi Jima Fasarakisa Hilliarda.
fjsj
@JonnyWaffles zobacz odpowiedź Jima i te pytania i odpowiedzi stackoverflow.com/questions/50872498/…
Chris_Rands
3
Jeśli chcesz, aby Twój kod działał tak samo w wersjach 2.7 i 3.6 / 3.7 +, musisz użyć OrdersDict
Boatcoder
3
Prawdopodobnie niedługo pojawi się „UnorderedDict” dla osób, które lubią sobie
radzić ze swoimi nagraniami ze
9

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.

rkengler
źródło