Dlaczego kolejność w słownikach i zestawach jest dowolna?

Nie rozumiem, w jaki sposób zapętlenie w słowniku lub ustawienie w Pythonie odbywa się w „arbitralnej” kolejności.

To znaczy, to język programowania, więc wszystko w języku musi być w 100% określone, prawda? Python musi mieć jakiś algorytm, który decyduje, która część słownika lub zestawu zostanie wybrana, pierwsza, druga i tak dalej.

czego mi brakuje?

Uwaga: ta odpowiedź została napisana przed dictzmianą implementacji typu, w Pythonie 3.6. Większość szczegółów implementacji w tej odpowiedzi nadal ma zastosowanie, ale kolejność wyświetlania kluczy w słownikach nie jest już określana przez wartości skrótu. Zestaw implementacji pozostaje niezmieniony.

Kolejność nie jest dowolna, ale zależy od historii wstawiania i usuwania słownika lub zestawu, a także od konkretnej implementacji Pythona. W pozostałej części tej odpowiedzi słowo „słownik” można również odczytać jako „zestaw”; zestawy są implementowane jako słowniki zawierające tylko klucze i bez wartości.

Klucze są mieszane, a wartości skrótu są przypisywane do gniazd w tabeli dynamicznej (może rosnąć lub zmniejszać się w zależności od potrzeb). Ten proces mapowania może prowadzić do kolizji, co oznacza, że ​​klucz będzie musiał zostać umieszczony w następnej szczelinie na podstawie tego, co już tam jest.

Wyświetlanie zawartości pętli nad gniazdami, więc klucze są wymienione w kolejności, w jakiej znajdują się obecnie w tabeli.

Weźmy na przykład klucze 'foo'i 'bar'przyjmijmy, że rozmiar stołu to 8 gniazd. W Pythonie 2.7 hash('foo')jest -4177197833195190597, hash('bar')jest 327024216814240868. Modulo 8, co oznacza, że ​​te dwa klucze są umieszczone w gniazdach 3 i 4, a następnie:

>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4

To informuje ich kolejność aukcji:

>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}

Wszystkie pola z wyjątkiem 3 i 4 są puste, a pętla nad tabelą zawiera najpierw gniazdo 3, a następnie miejsce 4, więc 'foo'zostało wymienione wcześniej 'bar'.

bara bazjednak mają wartości hash, które są dokładnie 8 od siebie, a tym samym map do tej samej szczeliny 4:

>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4

Ich kolejność zależy teraz od tego, który klucz został włożony jako pierwszy; drugi klucz będzie musiał zostać przeniesiony do następnego gniazda:

>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}

Kolejność stołów różni się tutaj, ponieważ jeden lub drugi klucz został umieszczony jako pierwszy.

Techniczna nazwa podstawowej struktury używanej przez CPython (najczęściej używana implementacja Pythona) to tablica mieszająca , która używa otwartego adresowania. Jeśli jesteś ciekawy i wystarczająco dobrze rozumiesz C, spójrz na implementację C, aby poznać wszystkie (dobrze udokumentowane) szczegóły. Możesz również obejrzeć prezentację Pycon 2010 autorstwa Brandona Rhodesa o tym, jak dictdziała CPython , lub pobrać kopię Beautiful Code , która zawiera rozdział poświęcony implementacji napisany przez Andrew Kuchlinga.

Należy zauważyć, że od wersji Python 3.3 używane jest również losowe ziarno mieszania, co sprawia, że ​​kolizje skrótów są nieprzewidywalne, aby zapobiec pewnym typom odmowy usługi (gdy atakujący powoduje, że serwer Pythona przestaje odpowiadać, powodując masowe kolizje skrótów). Oznacza to, że kolejność danego słownika lub zestawu zależy wtedy również od losowego ziarna mieszania dla bieżącego wywołania Pythona.

Inne implementacje mogą swobodnie używać innej struktury dla słowników, o ile spełniają udokumentowany dla nich interfejs Pythona, ale uważam, że wszystkie dotychczasowe implementacje używają odmiany tablicy skrótów.

CPython 3.6 wprowadza nową dict implementację, która utrzymuje kolejność wstawiania, jest szybsza i bardziej wydajna w pamięci do rozruchu. Zamiast utrzymywać dużą, rzadką tabelę, w której każdy wiersz odwołuje się do przechowywanej wartości skrótu oraz obiektów klucza i wartości, nowa implementacja dodaje mniejszą tablicę skrótów, która odwołuje się tylko do indeksów w oddzielnej `` gęstej '' tabeli (takiej, która zawiera tylko tyle wierszy ponieważ istnieją rzeczywiste pary klucz-wartość) i to zagęszczona tabela przedstawia listę zawartych elementów w kolejności. Zobacz propozycję dla Python-Dev, aby uzyskać więcej informacji . Zauważ, że w Pythonie 3.6 jest to uważane za szczegół implementacji, Python-the-language nie określa, że ​​inne implementacje muszą zachować porządek. Zmieniło się to w Pythonie 3.7, gdzie ten szczegół został podniesiony do rangi specyfikacji języka ; aby jakakolwiek implementacja była właściwie kompatybilna z Pythonem 3.7 lub nowszym, musi skopiować to zachowanie zachowujące kolejność. Mówiąc wprost: ta zmiana nie dotyczy zestawów, ponieważ zestawy mają już „małą” strukturę skrótu.

Python 2.7 i nowsze zawierają również OrderedDictklasę , podklasę, dictktóra dodaje dodatkową strukturę danych do rejestrowania kolejności kluczy. Za cenę pewnej szybkości i dodatkowej pamięci, ta klasa pamięta, w jakiej kolejności wstawiłeś klucze; lista kluczy, wartości lub elementów zrobi to w tej kolejności. Używa podwójnie połączonej listy przechowywanej w dodatkowym słowniku, aby skutecznie aktualizować zamówienie. Zobacz post Raymonda Hettingera przedstawiający pomysł . OrderedDictobiekty mają inne zalety, takie jak możliwość ponownego zamówienia .

Jeśli chciałeś zamówić zestaw, możesz zainstalować osetpakiet ; działa na Pythonie 2.5 i nowszych.

Jest to bardziej odpowiedź na Python 3.41 Zestaw przed zamknięciem jako duplikat.

Inni mają rację: nie polegaj na zamówieniu. Nawet nie udawaj, że istnieje.

To powiedziawszy, jest jedna rzecz, na której możesz polegać:

list(myset) == list(myset)

Oznacza to, że kolejność jest stabilna .

Zrozumienie, dlaczego istnieje postrzegany porządek, wymaga zrozumienia kilku rzeczy:

• Że Python używa zestawów skrótów ,

• Jak zestaw hash CPythona jest przechowywany w pamięci i

• Jak haszowane są liczby

Z góry:

ZA skrótów to metoda przechowywania losowych danych z naprawdę szybkimi czasami wyszukiwania.

Ma tablicę podstawową:

# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6

Zignorujemy specjalny obiekt atrapy, który istnieje tylko po to, aby ułatwić sobie usuwanie usunięć, ponieważ nie będziemy usuwać z tych zestawów.

Aby mieć naprawdę szybkie wyszukiwanie, wykonujesz magię, aby obliczyć hash z obiektu. Jedyną zasadą jest to, że dwa równe obiekty mają ten sam skrót. (Ale jeśli dwa obiekty mają ten sam skrót, mogą być nierówne).

Następnie tworzysz indeks, biorąc moduł przez długość tablicy:

hash(4) % len(storage) = index 2

To sprawia, że ​​dostęp do elementów jest naprawdę szybki.

Hashe to tylko większość historii, ponieważ hash(n) % len(storage)i hash(m) % len(storage)mogą skutkować tą samą liczbą. W takim przypadku można spróbować rozwiązać konflikt za pomocą kilku różnych strategii. CPython używa „liniowego sondowania” 9 razy przed wykonaniem skomplikowanych czynności, więc będzie wyglądał na lewo od slotu do 9 miejsc zanim zacznie szukać gdzie indziej.

Zestawy skrótów CPythona są przechowywane w następujący sposób:

• Zestaw skrótu nie może być zapełniony w więcej niż 2/3 . Jeśli jest 20 elementów, a tablica podkładowa ma 30 elementów, rozmiar magazynu zapasowego zostanie zmieniony na większy. Dzieje się tak, ponieważ kolizje występują częściej w małych sklepach pomocniczych, a kolizje wszystko spowalniają.

• Magazyn zapasowy zmienia rozmiar w potęgach 4, zaczynając od 8, z wyjątkiem dużych zestawów (50 000 elementów), które zmieniają rozmiar w potęgach dwóch: (8, 32, 128, ...).

Więc kiedy tworzysz tablicę, magazyn zapasowy ma długość 8. Kiedy jest zapełniony w 5 i dodasz element, będzie on na krótko zawierał 6 elementów. 6 > ²⁄₃·8więc to wyzwala zmianę rozmiaru, a magazyn zapasowy zwiększa się czterokrotnie do rozmiaru 32.

Wreszcie hash(n)zwraca tylko nliczby (z wyjątkiem tego, -1który jest specjalny).

Spójrzmy więc na pierwszą:

v_set = {88,11,1,33,21,3,7,55,37,8}

len(v_set)wynosi 10, więc magazyn zapasowy ma co najmniej 15 (+1) po dodaniu wszystkich elementów . Odpowiednia potęga 2 to 32. Tak więc magazyn zapasowy to:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

Mamy

hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1)  % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3)  % 32 = 3
hash(7)  % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8)  % 32 = 8

więc te wstawki jako:

__  1 __  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
   33 ← Can't also be where 1 is;
        either 1 or 33 has to move

Spodziewalibyśmy się więc takiego zamówienia

{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}

z 1 lub 33, które nie są na początku gdzie indziej. Będzie to używać sondowania liniowego, więc będziemy mieć albo:

       ↓
__  1 33  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

lub

       ↓
__ 33  1  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

Możesz oczekiwać, że 33 będzie tym, który został przesunięty, ponieważ 1 już tam był, ale ze względu na zmianę rozmiaru, która ma miejsce podczas budowania zestawu, tak nie jest. Za każdym razem, gdy zestaw zostanie przebudowany, już dodane elementy są skutecznie zmieniane.

Teraz możesz zobaczyć, dlaczego

{7,5,11,1,4,13,55,12,2,3,6,20,9,10}

może być w porządku. Jest 14 elementów, więc magazyn zapasowy ma co najmniej 21 + 1, co oznacza 32:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

Od 1 do 13 hashów w pierwszych 13 slotach. 20 trafia na miejsce 20.

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __

55 trafia w slocie, hash(55) % 32czyli 23:

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __

Gdybyśmy zamiast tego wybrali 50, spodziewalibyśmy się

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __

A oto i oto:

{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
#>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}

pop jest implementowany po prostu przez wygląd rzeczy: przechodzi przez listę i wyświetla pierwszą.

To wszystko szczegóły implementacji.

„Arbitralny” to nie to samo, co „nieokreślony”.

Mówią, że nie ma użytecznych właściwości kolejności iteracji słownika, które są „w interfejsie publicznym”. Prawie na pewno istnieje wiele właściwości kolejności iteracji, które są w pełni określone przez kod, który obecnie implementuje iterację słownika, ale autorzy nie obiecują ci ich jako czegoś, czego możesz użyć. Daje im to większą swobodę zmiany tych właściwości między wersjami Pythona (lub nawet w innych warunkach pracy lub całkowicie losowo w czasie wykonywania) bez obawy, że program się zepsuje.

Zatem jeśli piszesz program, który zależy od dowolnej właściwości w jakimkolwiek porządku słownikowym, to "zrywasz umowę" na używanie typu słownikowego, a programiści Pythona nie obiecują, że to zawsze zadziała, nawet jeśli wydaje się działać na razie, kiedy to przetestujesz. Jest to w zasadzie odpowiednik polegania na „niezdefiniowanym zachowaniu” w C.

Pozostałe odpowiedzi na to pytanie są doskonałe i dobrze napisane. PO pyta „jak”, co interpretuję jako „jak im ujdzie na sucho” lub „dlaczego”.

Dokumentacja Pythona mówi, że słowniki nie są uporządkowane, ponieważ słownik Pythona implementuje tablicę asocjacyjną typu danych abstrakcyjnych . Jak mówią

kolejność zwrotu wiązań może być dowolna

Innymi słowy, student informatyki nie może zakładać, że tablica asocjacyjna jest uporządkowana. To samo dotyczy zestawów matematycznych

kolejność, w jakiej są wymienione elementy zestawu, nie ma znaczenia

i informatyka

zestaw to abstrakcyjny typ danych, który może przechowywać określone wartości bez określonej kolejności

Implementacja słownika przy użyciu tablicy skrótów jest szczegółem implementacyjnym, który jest interesujący, ponieważ ma takie same właściwości, jak tablice asocjacyjne, jeśli chodzi o kolejność.

Python używa tablicy skrótów do przechowywania słowników, więc nie ma porządku w słownikach lub innych iterowalnych obiektach, które używają tablicy skrótów.

Ale jeśli chodzi o indeksy elementów w obiekcie haszującym, python oblicza indeksy na podstawie następującego kodu whashtable.c :

key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);

W związku z tym, ponieważ wartość skrótu liczb całkowitych jest samą liczbą całkowitą ^* indeks jest oparty na liczbie ( ht->num_buckets - 1jest stałą), więc indeks obliczany jest za pomocą funkcji Bitwise i między (ht->num_buckets - 1)a samą liczbą ^* (oczekuj dla -1, której hash wynosi -2 ) i dla innych obiektów z ich wartością skrótu.

rozważ następujący przykład z settym użyciem tablicy skrótów:

>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])

Dla numeru 33mamy:

33 & (ht->num_buckets - 1) = 1

To właściwie jest:

'0b100001' & '0b111'= '0b1' # 1 the index of 33

Uwaga w tym przypadku (ht->num_buckets - 1)to 8-1=7lub0b111 .

I dla 1919:

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919

I dla 333:

'0b101001101' & '0b111' = '0b101' # 5 the index of 333

Aby uzyskać więcej informacji na temat funkcji skrótu w Pythonie, dobrze jest przeczytać następujące cytaty z kodu źródłowego Pythona :

Główne subtelności na przyszłość: większość schematów skrótu zależy od posiadania „dobrej” funkcji skrótu w sensie symulowania losowości. Python tego nie robi: jego najważniejsze funkcje haszujące (dla ciągów znaków i int) są bardzo regularne w typowych przypadkach:

>>> map(hash, (0, 1, 2, 3))
  [0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
  [-1658398457, -1658398460, -1658398459, -1658398462]

To niekoniecznie jest złe! Wręcz przeciwnie, w tabeli o rozmiarze 2 ** i przyjmowanie najmniej znaczących bitów i jako początkowego indeksu tabeli jest niezwykle szybkie i nie ma żadnych kolizji w przypadku dykt indeksowanych przez ciągły zakres liczb całkowitych. To samo jest w przybliżeniu prawdziwe, gdy klucze są ciągami „następujących po sobie”. To daje w typowych przypadkach zachowanie lepsze niż przypadkowe i jest to bardzo pożądane.

OTOH, gdy występują kolizje, tendencja do wypełniania ciągłych wycinków tablicy skrótów sprawia, że ​​dobra strategia rozwiązywania kolizji ma kluczowe znaczenie. Podatne jest również pobranie tylko ostatnich i bitów kodu skrótu: na przykład potraktuj listę [i << 16 for i in range(20000)]jako zestaw kluczy. Ponieważ int są ich własnymi kodami skrótu, a to pasuje do słowa o rozmiarze 2 ** 15, ostatnie 15 bitów każdego kodu skrótu ma wartość 0: wszystkie są mapowane na ten sam indeks tabeli.

Ale obsługa nietypowych przypadków nie powinna spowalniać tych zwykłych, więc i tak bierzemy tylko ostatnie kawałki. Resztą zajmie się rozwiązanie kolizji. Jeśli zwykle znajdujemy klucz, którego szukamy za pierwszym razem (i okazuje się, że zwykle to robimy - współczynnik obciążenia stołu jest utrzymywany poniżej 2/3, więc szanse są solidnie na naszą korzyść), to najlepiej jest, aby początkowe obliczenia indeksu były tanie.

_{* Funkcja skrótu dla klasy int:}

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value = -2
        return value

Począwszy od Pythona 3.7 (a już w CPythonie 3.6 ), elementy słownika pozostają w kolejności, w jakiej zostały wstawione .