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
źródło
**kwargs
i jako takie użyte sformułowanie jest dyplomatyczne:**kwargs
w 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życiaOrderedDict
wewnętrznego) oraz jako sposób zasygnalizowania, że nie powinno to zależeć od faktu, żedict
nie jest ono uporządkowane.Odpowiedzi:
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ć,
OrderedDict
jeś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 :
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.
Zasadniczo poprzez utrzymanie dwóch tablic .
Pierwsza tablica
dk_entries
zawiera 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_indices
zawiera wskaźniki dladk_entries
tablicy (czyli wartości wskazujące pozycję odpowiedniego wpisu wdk_entries
). Ta tablica działa jak tablica skrótów. Gdy klucz jest mieszany, prowadzi on do jednego z przechowywanych indeksów,dk_indices
a odpowiedni wpis jest pobierany przez indeksowaniedk_entries
. Ponieważ przechowywane są tylko indeksy, typ tej tablicy zależy od ogólnego rozmiaru słownika (od typuint8_t
(1
bajt) doint32_t
/int64_t
(4
/8
bajty) w32
/64
kompilacjach bitowych)W poprzedniej implementacji konieczne było przydzielenie rzadkiej tablicy typu
PyDictKeyEntry
i rozmiarudk_size
; Niestety, to również spowodowało dużo pustej przestrzeni ponieważ tablica nie wolno było mieć więcej niż2/3 * dk_size
pełny ze względu na wydajność . (a puste miejsce wciąż miałoPyDictKeyEntry
rozmiar!).Teraz tak nie jest, ponieważ przechowywane są tylko wymagane wpisy (te, które zostały wstawione) i zachowana jest rzadka tablica typu
intX_t
(wX
zależności od rozmiaru nagrania)2/3 * dk_size
pełna. Puste miejsce zmieniło się z typuPyDictKeyEntry
naintX_t
.Tak więc, oczywiście, tworzenie rzadkiej tablicy typu
PyDictKeyEntry
wymaga znacznie więcej pamięci niż rzadka tablica do przechowywaniaint
s.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.
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
dict
obiekt 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 (==
,!=
).dict
Obecnie 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.
źródło
entries
zmieniono rozmiar listy? czy jest zachowane puste miejsce? czy od czasu do czasu jest kompresowany?DKIX_DUMMY
wartość-2
i wpis wentry
tablicy 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żej2/3
progu, zostanie przeprowadzona zmiana rozmiaru. Może to prowadzić do zmniejszania się zamiast wzrostu, jeśliDUMMY
istnieje wiele wpisów.d = {i:i for i in range(100)}
a.pop
wszystkie elementy nie zostaną wstawione, rozmiar się nie zmieni. Po ponownym dodaniud[1] = 1
obliczany jest odpowiedni rozmiar i zmienia rozmiar dykta.dict
byciu zamówionym”,dict
nie są uporządkowane w tym sensie,OrderedDict
że są. Ważną kwestią jest równość.dict
mają niewrażliwe na porządek==
,OrderedDict
mają wrażliwe na porządek. ZrzutyOrderedDict
i zmianadicts
na 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ć wOrderedDict
s, jest jego implementacja.Poniżej znajduje się odpowiedź na pierwsze pytanie:
Myślę, że to zdanie z dokumentacji wystarczy, aby odpowiedzieć na twoje pytanie
dict
nie 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
źródło
Aktualizacja: Guido van Rossum ogłosił na liście mailowej, że począwszy od Pythona 3.7
dict
s we wszystkich implementacjach Pythona musi zachowywać kolejność wstawiania.źródło
move_to_end
metodę, a jej równość jest wrażliwa na kolejność: docs.python.org/3/library/… . Zobacz notatkę na temat odpowiedzi Jima Fasarakisa Hilliarda.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
.Nie widzę żadnej wzmianki o operatorze równości ani innych cechach,
OrderedDict
więc wciąż nie są one do końca takie same.źródło