„Dziwne” porządkowanie zestawów w pythonie

Kiedy konwertuję listę Python 3.8.0 na zestaw, wynikowa kolejność zestawów * jest wysoce uporządkowana w nietrywialny sposób. Jak ta struktura jest wydobywana z listy pseudolosowej?

W ramach prowadzonego eksperymentu generuję losowy zestaw. Byłem zaskoczony widząc, że kreślenie zestawu nagle pokazało nieoczekiwaną strukturę liniową w zestawie. Zastanawiają mnie więc dwie rzeczy - dlaczego konwersja na zestaw wyników ma uporządkowanie *, co w końcu uwypukla tę strukturę; i, w mniejszym stopniu, dlaczego zestaw pseudolosowy ma w ogóle tę „ukrytą” strukturę?

Kod:

X = [randrange(250) for i in range(30)]
print(X)
print(set(X))

które wyjścia, na przykład

[238, 202, 245, 94, 111, 106, 148, 164, 154, 113, 128, 10, 196, 141, 69, 38, 106, 8, 40, 53, 160, 87, 85, 13, 38, 147, 204, 50, 162, 91]

{128, 8, 10, 141, 13, 147, 148, 154, 160, 162, 164, 38, 40, 50, 53, 196, 69, 202, 204, 85, 87, 91, 94, 106, 238, 111, 113, 245}

Wykres ** z powyższej listy wygląda dość losowo, zgodnie z oczekiwaniami:

podczas gdy wykreślanie zestawu (zgodnie z kolejnością na wyjściu) wykazuje strukturę obecną w zestawie:

To zachowanie jest w 100% spójne na mojej maszynie (więcej przykładów poniżej) z wartościami 250 i 30 użytymi w powyższym kodzie (przykład, którego użyłem, nie został wybrany - to tylko ostatni, który uruchomiłem). Strojenie tych wartości czasami powoduje nieco inną strukturę (np. Podzbiór trzech progresji arytmetycznych *** zamiast dwóch).

Czy jest to powtarzalne na maszynach innych ludzi? Oczywiście, że taka struktura istnieje, wydaje się wskazywać na niezbyt wielkie generowanie liczb pseudolosowych, ale to nie wyjaśnia, w jaki sposób konwersja na zbiór w pewnym sensie „wydobywałaby” tę strukturę. O ile mi wiadomo, nie ma formalnej gwarancji, że uporządkowanie zestawu (po przekonwertowaniu z listy) jest deterministyczne (a nawet jeśli tak jest, nie jest wykonywane wyrafinowane porządkowanie w tle). Jak to się dzieje ?!

(*): Wiem, że zbiory są nieuporządkowanymi zbiorami, ale mam na myśli „uporządkowany” w tym sensie, że podczas wywoływania printinstrukcji zestaw jest wyprowadzany w pewnej kolejności, która konsekwentnie podkreśla podstawową strukturę zbioru.

(**): Te wykresy pochodzą z Wolfram Alpha. Dwa kolejne przykłady są poniżej:

(***): Dwa wykresy przy zmianie zakresu liczb losowych z 250 na 500:

Zasadniczo wynika to z dwóch rzeczy:

• Zestaw w Pythonie jest implementowany za pomocą tablicy hashtable ,
• Skrót liczby całkowitej jest liczbą całkowitą.

Dlatego wskaźnik, że liczba całkowita pojawia się w tablicy bazowej, będzie określony przez wartość liczby całkowitej, modulo długości tablicy bazowej. Tak więc liczby całkowite będą miały tendencję do pozostawania w porządku rosnącym, gdy umieścisz ich ciągły zakres w zestawie:

>>> list(set(range(10000))) == list(range(10000))
True # this can't be an accident!

Jeśli nie masz wszystkich liczb z sąsiedniego zakresu, wówczas wchodzi w grę część „moduł długości leżącej poniżej tablicy”:

>>> r = range(0, 50, 4)
>>> set(r)
{0, 32, 4, 36, 8, 40, 12, 44, 16, 48, 20, 24, 28}
>>> sorted(r, key=lambda x: x % 32)
[0, 32, 4, 36, 8, 40, 12, 44, 16, 48, 20, 24, 28]

Sekwencja jest przewidywalna, jeśli znasz długość podstawowej tablicy i (deterministyczny) algorytm dodawania elementów. W tym przypadku długość tablicy wynosi 32, ponieważ początkowo wynosi 8 i jest czterokrotnie podczas dodawania elementów.

Z wyjątkiem blipu pod koniec (ponieważ liczb 52 i 56 nie ma w zestawie), zakres jest podzielony na dwie sekwencje 0, 4, 8, ...i 32, 36, 40, ...które występują naprzemiennie, ponieważ skróty, które same są wartościami liczb, są brane modulo 32 do wyboru indeksy w tablicy. Są kolizje; na przykład 4 i 36 są równe modulo 32, ale 4 zostało dodane do zestawu jako pierwsze, więc 36 kończy się na innym indeksie.

Oto wykres dla tej sekwencji. Struktura na twoich wykresach jest tylko bardziej głośną wersją, ponieważ generowałeś liczby losowo, a nie z zakresu z krokiem.

Liczba przeplecionych sekwencji będzie zależeć od wielkości zbioru proporcjonalnie do długości zakresu, z którego próbkowane są liczby, ponieważ określa to, ile razy długość zakresu „owija się” modulo długości podstawowej tablicy tablicy mieszającej. Oto przykład z trzech przeplecionych sekwencji 0, 6, 12, ..., 66, 72, 78, ...oraz 36, 42, 48, ...:

>>> set(range(0, 90, 6))
{0, 66, 36, 6, 72, 42, 12, 78, 48, 18, 84, 54, 24, 60, 30}