Ordre «bizarre» des ensembles en python

Lorsque je convertis une liste Python 3.8.0 en un ensemble, l'ordre des ensembles résultant * est hautement structuré de manière non triviale. Comment cette structure est-elle extraite de la liste pseudo-aléatoire?

Dans le cadre d'une expérience que je lance, je génère un ensemble aléatoire. J'ai été surpris de voir que le tracé de l'ensemble montrait soudainement une structure linéaire inattendue dans l'ensemble. Il y a donc deux choses qui m'intriguent - pourquoi la conversion en résultat d'ensemble a-t-elle un ordre * qui finit par mettre en évidence cette structure; et, dans une moindre mesure, pourquoi l'ensemble pseudo-aléatoire a-t-il cette structure "cachée"?

Le code:

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

qui sort, par exemple

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

Un tracé ** de la liste ci-dessus semble assez aléatoire, comme prévu:

tandis que le traçage de l'ensemble (tel qu'il est ordonné dans la sortie) présente la structure présente dans l'ensemble:

Ce comportement 100% cohérent sur ma machine (plus d'exemples ci-dessous) avec les valeurs 250 et 30 utilisées dans le code ci-dessus (l'exemple que j'ai utilisé n'est pas choisi par les cerises - c'est juste le dernier que j'ai exécuté). Le réglage de ces valeurs entraîne parfois une structure légèrement différente (par exemple, un sous-ensemble de trois progressions arithmétiques *** au lieu de deux).

Est-ce reproductible sur les machines d'autres personnes? Bien sûr, le fait qu'une telle structure existe semble indiquer une génération de nombres pseudo-aléatoires pas si grande, mais cela n'explique pas comment la conversion en un ensemble «extrait» en quelque sorte cette structure. Pour autant que je sache, il n'y a aucune garantie formelle que l'ordre d'un ensemble (lorsqu'il est converti à partir d'une liste) est déterministe (et même s'il l'est, aucun ordre sophistiqué n'est effectué en arrière-plan). Alors comment ça se passe?!

(*): Je sais, les ensembles sont des collections non ordonnées, mais je veux dire "ordonné" dans le sens où, lors de l'appel de l' printinstruction, l'ensemble est sorti dans un ordre qui met en évidence de manière cohérente la structure d'ensemble sous-jacente.

(**): Ces parcelles proviennent de Wolfram Alpha. Voici deux autres exemples:

(***): Deux tracés lors du changement de la plage des nombres aléatoires de 250 à 500:

Fondamentalement, cela est dû à deux choses:

• Un ensemble en Python est implémenté à l'aide d'une table de hachage ,
• Le hachage d'un entier est l'entier lui-même.

Par conséquent, l'indice qu'un entier apparaît dans le tableau sous-jacent sera déterminé par la valeur de l'entier, modulo la longueur du tableau sous-jacent. Ainsi, les entiers ont tendance à rester dans l'ordre croissant lorsque vous en mettez une plage contiguë dans un ensemble:

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

Si vous n'avez pas tous les nombres d'une plage contiguë, alors la partie "modulo la longueur du tableau sous-jacent" entre en jeu:

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

La séquence est prévisible si vous connaissez la longueur du tableau sous-jacent et l'algorithme (déterministe) pour ajouter des éléments. Dans ce cas, la longueur du tableau est de 32, car elle est initialement de 8 et est quadruplée lors de l'ajout d'éléments.

Sauf pour un blip vers la fin (parce que les nombres 52 et 56 ne sont pas dans l'ensemble), la plage est divisée en deux séquences 0, 4, 8, ...et 32, 36, 40, ...qui alternent parce que les hachages, qui sont les valeurs des nombres eux-mêmes, sont pris modulo 32 pour choisir indices dans le tableau. Il y a des collisions; par exemple, 4 et 36 sont égaux à modulo 32, mais 4 a été ajouté à l'ensemble en premier afin que 36 se retrouve à un indice différent.

Voici un tableau pour cette séquence. La structure de vos graphiques est juste une version plus bruyante, car vous avez généré vos nombres au hasard plutôt qu'à partir d'une plage avec un pas.

Le nombre de séquences entrelacées dépendra de la taille de l'ensemble proportionnellement à la longueur de la plage à partir de laquelle les nombres sont échantillonnés, car cela détermine combien de fois la longueur de la plage "enveloppe" modulo la longueur du tableau sous-jacent de la table de hachage. Voici un exemple avec trois séquences entrelacées 0, 6, 12, ..., 66, 72, 78, ...et 36, 42, 48, ...:

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