Ordenação 'bizarra' de conjuntos em python

Quando converto uma lista Python 3.8.0 em um conjunto, a ordenação resultante * é altamente estruturada de maneira não trivial. Como essa estrutura está sendo extraída da lista pseudo-aleatória?

Como parte de um experimento que estou executando, estou gerando um conjunto aleatório. Fiquei surpreso ao ver que a plotagem do conjunto de repente mostrou uma estrutura linear inesperada no conjunto. Portanto, há duas coisas que me intrigam: por que a conversão para um resultado definido tem uma ordem * que acaba destacando essa estrutura; e, em menor grau, por que o conjunto pseudo-aleatório tem essa estrutura "oculta"?

O código:

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

quais saídas, por exemplo

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

Um gráfico ** da lista acima parece bastante aleatório, como esperado:

enquanto a plotagem do conjunto (conforme ordenada na saída) exibe a estrutura presente no conjunto:

Esse comportamento é 100% consistente na minha máquina (mais exemplos abaixo) com os valores 250 e 30 usados ​​no código acima (o exemplo que eu usei não é escolhido por cereja - é apenas o último que eu executei). O ajuste desses valores às vezes resulta em uma estrutura ligeiramente diferente (por exemplo, um subconjunto de três progressões aritméticas *** em vez de duas).

Isso é reproduzível nas máquinas de outras pessoas? É claro que essa estrutura existe parece indicativa de uma geração de números pseudoaleatórios não tão boa, mas isso não explica como a conversão em um conjunto "de certa forma" extrairia essa estrutura. Tanto quanto sei, não há garantia formal de que a ordem de um conjunto (quando convertida de uma lista) seja determinística (e mesmo que seja, não há nenhuma ordem sofisticada sendo executada em segundo plano). Então, como isso está acontecendo ?!

(*): Eu sei que conjuntos são coleções não ordenadas, mas quero dizer "ordenados" no sentido de que, ao chamar a printdeclaração, o conjunto é produzido em alguma ordem que destaca consistentemente a estrutura subjacente dos conjuntos.

(**): esses gráficos são da Wolfram Alpha. Mais dois exemplos estão abaixo:

(***): dois gráficos ao alterar o intervalo dos números aleatórios de 250 para 500:

Basicamente, isso ocorre por duas coisas:

• Um conjunto em Python é implementado usando uma hashtable ,
• O hash de um número inteiro é o próprio número inteiro.

Portanto, o índice que um número inteiro aparece na matriz subjacente será determinado pelo valor inteiro, modulando o comprimento da matriz subjacente. Portanto, os números inteiros tendem a permanecer em ordem crescente quando você coloca um intervalo contíguo deles em um conjunto:

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

Se você não possui todos os números de um intervalo contíguo, a parte "módulo do comprimento da matriz subjacente" entra em jogo:

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

A sequência é previsível se você souber o comprimento da matriz subjacente e o algoritmo (determinístico) para adicionar elementos. Nesse caso, o comprimento da matriz é 32, porque é inicialmente 8 e é quadruplicado enquanto os elementos são adicionados.

Exceto por um sinal próximo ao final (porque os números 52 e 56 não estão no conjunto), o intervalo é dividido em duas seqüências 0, 4, 8, ...e 32, 36, 40, ...que se alternam porque os hashes, que são os próprios valores dos números, são tomados no módulo 32 para escolher índices na matriz. Existem colisões; por exemplo, 4 e 36 são iguais ao módulo 32, mas 4 foi adicionado primeiro ao conjunto para que 36 termine em um índice diferente.

Aqui está um gráfico para esta sequência. A estrutura em seus gráficos é apenas uma versão mais ruidosa, porque você gerou seus números aleatoriamente, e não a partir de um intervalo com uma etapa.

O número de sequências intercaladas dependerá do tamanho do conjunto proporcional ao comprimento do intervalo em que os números são amostrados, uma vez que determina quantas vezes o comprimento do intervalo "envolve" o módulo do comprimento da matriz subjacente da hashtable. Aqui está um exemplo com três seqüências intercaladas 0, 6, 12, ..., 66, 72, 78, ...e 36, 42, 48, ...:

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