'Aneh' memesan set dalam python

Ketika saya mengonversi daftar Python 3.8.0 ke satu set, set pemesanan yang dihasilkan * sangat terstruktur dengan cara yang tidak sepele. Bagaimana struktur ini diekstraksi dari daftar pseudo-acak?

Sebagai bagian dari eksperimen yang saya jalankan, saya membuat set acak. Saya terkejut melihat bahwa merencanakan himpunan tiba-tiba menunjukkan struktur linier yang tidak terduga dalam himpunan. Jadi ada dua hal yang membingungkan saya - mengapa mengkonversi ke hasil yang ditetapkan memiliki urutan * yang akhirnya menyoroti struktur ini; dan, pada tingkat lebih rendah mengapa set pseudo-acak memiliki struktur "tersembunyi" ini sama sekali?

Kode:

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

yang menghasilkan, misalnya

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

Plot ** dari daftar di atas terlihat cukup acak, seperti yang diharapkan:

sedangkan merencanakan himpunan (seperti yang diperintahkan dalam output) menunjukkan struktur yang ada di himpunan:

Perilaku ini 100% konsisten pada mesin saya (lebih banyak contoh di bawah) dengan nilai 250 dan 30 yang digunakan dalam kode di atas (contoh yang saya gunakan bukan cherry pick - itu hanya yang terakhir saya jalankan). Tuning nilai-nilai ini kadang-kadang menghasilkan struktur yang sedikit berbeda (misalnya subset dari tiga perkembangan aritmatika *** bukan dua).

Apakah ini dapat direproduksi di komputer orang lain? Tentu saja, bahwa struktur seperti itu nampak sebagai indikasi dari generasi nomor pseudo-acak yang tidak terlalu besar, tetapi ini tidak menjelaskan bagaimana mengkonversi ke suatu set dalam beberapa hal 'mengekstraksi' struktur ini. Sejauh yang saya ketahui, tidak ada jaminan resmi bahwa pemesanan set (ketika dikonversi dari daftar) adalah deterministik (dan bahkan jika itu, tidak ada pemesanan canggih yang dilakukan di latar belakang). Jadi bagaimana ini terjadi ?!

(*): Saya tahu, set koleksi unordered, tapi maksudku "memerintahkan" dalam arti bahwa, saat memanggil printpernyataan, himpunan adalah output dalam beberapa urutan yang secara konsisten menyoroti struktur set yang mendasarinya.

(**): Petak ini berasal dari Wolfram Alpha. Dua contoh lagi di bawah ini:

(***): Dua plot saat mengubah kisaran angka acak dari 250 menjadi 500:

Pada dasarnya, ini karena dua hal:

• Satu set Python diimplementasikan menggunakan hashtable ,
• Hash dari integer adalah integer itu sendiri.

Oleh karena itu, indeks yang muncul bilangan bulat dalam array yang mendasarinya akan ditentukan oleh nilai integer, modulo panjang array yang mendasarinya. Jadi, bilangan bulat akan cenderung tetap dalam urutan naik ketika Anda menempatkan rentang yang berdekatan di dalam satu set:

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

Jika Anda tidak memiliki semua angka dari rentang yang berdekatan, maka bagian "modulo panjang array yang mendasarinya" ikut bermain:

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

Urutannya dapat diprediksi jika Anda tahu panjang array yang mendasarinya, dan algoritma (deterministik) untuk menambahkan elemen. Dalam hal ini panjang array adalah 32, karena awalnya 8 dan empat kali lipat sementara elemen ditambahkan.

Kecuali untuk blip di dekat akhir (karena angka 52 dan 56 tidak ada di set), kisaran dibagi menjadi dua urutan 0, 4, 8, ...dan 32, 36, 40, ...yang bergantian karena hash, yang merupakan nilai angka itu sendiri, diambil modulo 32 untuk memilih indeks dalam array. Ada tabrakan; misalnya, 4 dan 36 adalah modulo 32 yang sama, tetapi 4 ditambahkan ke set pertama sehingga 36 berakhir pada indeks yang berbeda.

Berikut adalah bagan untuk urutan ini. Struktur dalam bagan Anda hanya versi yang lebih berisik, karena Anda membuat angka-angka Anda secara acak daripada dari rentang dengan langkah.

Jumlah urutan yang disatukan akan tergantung pada ukuran set secara proporsional dengan panjang rentang dari jumlah sampel, karena itu menentukan berapa kali panjang rentang "membungkus" modulo panjang array yang mendasari hashtable. Berikut adalah contoh dengan tiga urutan yang disatukan 0, 6, 12, ..., 66, 72, 78, ...dan 36, 42, 48, ...:

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