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:
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.