'Bizarre' Reihenfolge von Sets in Python

Wenn ich eine Python 3.8.0-Liste in eine Menge konvertiere, ist die resultierende Mengenreihenfolge * nicht trivial stark strukturiert. Wie wird diese Struktur aus der Pseudozufallsliste extrahiert?

Als Teil eines Experiments, das ich durchführe, generiere ich eine zufällige Menge. Ich war überrascht zu sehen, dass das Zeichnen des Sets plötzlich eine unerwartete lineare Struktur im Set zeigte. Es gibt also zwei Dinge, die mich verwirren: Warum hat die Konvertierung in ein festgelegtes Ergebnis eine Reihenfolge *, die diese Struktur hervorhebt? und in geringerem Maße, warum hat die Pseudozufallsmenge überhaupt diese "versteckte" Struktur?

Der Code:

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

welche Ausgänge zum Beispiel

[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}

Ein Plot ** der obigen Liste sieht erwartungsgemäß ziemlich zufällig aus:

Während das Zeichnen der Menge (wie in der Ausgabe angeordnet) die in der Menge vorhandene Struktur aufweist:

Dieses Verhalten stimmt auf meinem Computer zu 100% überein (weitere Beispiele unten) mit den im obigen Code verwendeten Werten 250 und 30 (das von mir verwendete Beispiel ist nicht von Kirschen gepflückt - es ist nur das letzte, das ich ausgeführt habe). Das Einstellen dieser Werte führt manchmal zu einer leicht unterschiedlichen Struktur (z. B. einer Teilmenge von drei arithmetischen Fortschritten *** anstelle von zwei).

Ist dies auf den Maschinen anderer Leute reproduzierbar? Natürlich scheint die Existenz einer solchen Struktur auf eine nicht so große Erzeugung von Pseudozufallszahlen hinzudeuten, aber dies erklärt nicht, wie die Konvertierung in eine Menge diese Struktur in gewissem Sinne "extrahieren" würde. Soweit mir bekannt ist, gibt es keine formale Garantie dafür, dass die Reihenfolge einer Menge (wenn sie aus einer Liste konvertiert wird) deterministisch ist (und selbst wenn dies der Fall ist, wird im Hintergrund keine ausgefeilte Reihenfolge durchgeführt). Wie passiert das?!

(*): Ich weiß, Mengen sind ungeordnete Sammlungen, aber ich meine "geordnet" in dem Sinne, dass beim Aufrufen der printAnweisung die Menge in einer Reihenfolge ausgegeben wird , die die zugrunde liegende Mengenstruktur konsistent hervorhebt.

(**): Diese Grundstücke stammen von Wolfram Alpha. Zwei weitere Beispiele sind unten aufgeführt:

(***): Zwei Diagramme beim Ändern des Bereichs der Zufallszahlen von 250 auf 500:

Grundsätzlich liegt dies an zwei Dingen:

• Ein Satz in Python wird mithilfe einer Hashtabelle implementiert .
• Der Hash einer Ganzzahl ist die Ganzzahl selbst.

Daher wird der Index, dass eine Ganzzahl im zugrunde liegenden Array angezeigt wird, durch den Wert der Ganzzahl bestimmt, modulo die Länge des zugrunde liegenden Arrays. Ganzzahlen bleiben also in aufsteigender Reihenfolge, wenn Sie einen zusammenhängenden Bereich von ihnen in eine Menge einfügen:

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

Wenn Sie nicht alle Zahlen aus einem zusammenhängenden Bereich haben, kommt der Teil "Modulo die Länge des zugrunde liegenden Arrays" ins Spiel:

>>> 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]

Die Sequenz ist vorhersehbar, wenn Sie die Länge des zugrunde liegenden Arrays und den (deterministischen) Algorithmus zum Hinzufügen von Elementen kennen. In diesem Fall beträgt die Länge des Arrays 32, da es anfänglich 8 ist und sich vervierfacht, während Elemente hinzugefügt werden.

Mit Ausnahme einer blip nahe dem Ende (weil die Zahlen 52 und 56 nicht in der Gruppe sind), wird der Bereich in zwei Sequenzen , 0, 4, 8, ...und 32, 36, 40, ...die sich abwechseln , da die Hash - Werte, die die Zahlen Werte selbst sind, getroffen werden modulo 32 zu wählen Indizes im Array. Es gibt Kollisionen; Zum Beispiel sind 4 und 36 gleich Modulo 32, aber 4 wurde zuerst zum Satz hinzugefügt, so dass 36 an einem anderen Index endet.

Hier ist eine Tabelle für diese Sequenz. Die Struktur in Ihren Diagrammen ist nur eine lautere Version, da Sie Ihre Zahlen eher zufällig als aus einem Bereich mit einem Schritt generiert haben.

Die Anzahl der verschachtelten Sequenzen hängt von der Größe des Satzes im Verhältnis zur Länge des Bereichs ab, aus dem die Zahlen abgetastet werden, da dies bestimmt, wie oft die Länge des Bereichs modulo die Länge des zugrunde liegenden Arrays der Hashtabelle "umschließt". Hier ist ein Beispiel mit drei verschachtelten Sequenzen 0, 6, 12, ..., 66, 72, 78, ...und 36, 42, 48, ...:

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