Mengapa saya mendapatkan banyak iterasi saat menambahkan dan menghapus dari set sementara iterasi?

Mencoba memahami Python for-loop, saya pikir ini akan memberikan hasil {1}untuk satu iterasi, atau hanya terjebak dalam infinite loop, tergantung pada apakah ia melakukan iterasi seperti dalam C atau bahasa lain. Tapi sebenarnya tidak.

>>> s = {0}
>>> for i in s:
...     s.add(i + 1)
...     s.remove(i)
...
>>> print(s)
{16}

Mengapa ia melakukan 16 iterasi? Dari mana hasil itu {16}berasal?

Ini menggunakan Python 3.8.2. Pada pypy itu membuat hasil yang diharapkan {1}.

Python tidak membuat janji tentang kapan (jika pernah) loop ini akan berakhir. Memodifikasi set selama iterasi dapat menyebabkan elemen dilewati, elemen berulang, dan keanehan lainnya. Jangan pernah mengandalkan perilaku seperti itu.

Semua yang akan saya katakan adalah detail implementasi, dapat berubah tanpa pemberitahuan. Jika Anda menulis sebuah program yang bergantung pada semua itu, program Anda dapat merusak kombinasi implementasi Python dan versi selain CPython 3.8.2.

Penjelasan singkat mengapa loop berakhir pada 16 adalah bahwa 16 adalah elemen pertama yang kebetulan ditempatkan pada indeks tabel hash yang lebih rendah daripada elemen sebelumnya. Penjelasan lengkapnya di bawah ini.

Tabel hash internal dari set Python selalu memiliki kekuatan 2 ukuran. Untuk tabel ukuran 2 ^ n, jika tidak ada tabrakan, elemen disimpan dalam posisi di tabel hash sesuai dengan n bit paling tidak signifikan dari hash mereka. Anda dapat melihat ini diterapkan di set_add_entry:

mask = so->mask;
i = (size_t)hash & mask;

entry = &so->table[i];
if (entry->key == NULL)
    goto found_unused;

Kebanyakan hasrat Python kecil untuk diri mereka sendiri; khususnya, semua int dalam hash tes Anda untuk diri mereka sendiri. Anda dapat melihat ini diterapkan di long_hash. Karena set Anda tidak pernah berisi dua elemen dengan bit rendah yang sama di hash, tidak ada tabrakan yang terjadi.

Set iterator Python melacak posisinya dalam set dengan indeks integer sederhana ke dalam tabel hash internal set. Ketika elemen berikutnya diminta, iterator mencari entri yang diisi dalam tabel hash mulai dari indeks itu, kemudian menetapkan indeks yang disimpan segera setelah entri yang ditemukan dan mengembalikan elemen entri. Anda dapat melihatnya di setiter_iternext:

while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
    i++;
si->si_pos = i+1;
if (i > mask)
    goto fail;
si->len--;
key = entry[i].key;
Py_INCREF(key);
return key;

Set Anda awalnya dimulai dengan tabel hash ukuran 8, dan pointer ke 0objek int di indeks 0 di tabel hash. Iterator juga diposisikan di indeks 0. Ketika Anda mengulanginya, elemen ditambahkan ke tabel hash, masing-masing di indeks berikutnya karena di situlah hash mereka mengatakan untuk meletakkannya, dan itu selalu indeks berikutnya yang dilihat iterator. Elemen yang dihapus memiliki penanda dummy yang disimpan di posisi lamanya, untuk tujuan resolusi tabrakan. Anda dapat melihat hal itu diimplementasikan di set_discard_entry:

entry = set_lookkey(so, key, hash);
if (entry == NULL)
    return -1;
if (entry->key == NULL)
    return DISCARD_NOTFOUND;
old_key = entry->key;
entry->key = dummy;
entry->hash = -1;
so->used--;
Py_DECREF(old_key);
return DISCARD_FOUND;

Ketika 4ditambahkan ke set, jumlah elemen dan boneka di set menjadi cukup tinggi yang set_add_entrymemicu membangun kembali tabel hash, memanggil set_table_resize:

if ((size_t)so->fill*5 < mask*3)
    return 0;
return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);

so->usedadalah jumlah entri yang diisi, non-dummy dalam tabel hash, yaitu 2, sehingga set_table_resizemenerima 8 sebagai argumen kedua. Berdasarkan ini, set_table_resize memutuskan ukuran tabel hash baru harus 16:

/* Find the smallest table size > minused. */
/* XXX speed-up with intrinsics */
size_t newsize = PySet_MINSIZE;
while (newsize <= (size_t)minused) {
    newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.
}

Itu membangun kembali tabel hash dengan ukuran 16. Semua elemen masih berakhir pada indeks lama mereka di tabel hash baru, karena mereka tidak memiliki bit tinggi yang diatur dalam hash mereka.

Ketika loop berlanjut, elemen terus ditempatkan di indeks berikutnya iterator akan terlihat. Membangun kembali tabel hash lain dipicu, tetapi ukuran baru masih 16.

Pola rusak ketika loop menambahkan 16 sebagai elemen. Tidak ada indeks 16 untuk menempatkan elemen baru di. 4 bit terendah dari 16 adalah 0000, menempatkan 16 pada indeks 0. Indeks tersimpan iterator adalah 16 pada titik ini, dan ketika loop meminta elemen berikutnya dari iterator, iterator melihat bahwa ia telah melewati akhir dari tabel hash.

Iterator mengakhiri loop pada titik ini, hanya menyisakan 16di set.

Saya percaya ini ada hubungannya dengan implementasi set python yang sebenarnya. Set menggunakan tabel hash untuk menyimpan item mereka dan iterasi di atas set berarti iterasi di atas baris tabel hash-nya.

Ketika Anda mengulang dan menambahkan item ke set Anda, hash baru sedang dibuat dan ditambahkan ke tabel hash sampai Anda mencapai nomor 16. Pada titik ini, angka berikutnya sebenarnya ditambahkan ke awal tabel hash dan bukan ke akhir. Dan karena Anda sudah mengulangi pada baris pertama tabel, loop iterasi berakhir.

Jawaban saya didasarkan pada ini salah satu pertanyaan serupa, itu benar-benar menunjukkan contoh yang sama persis ini. Saya sangat merekomendasikan membacanya untuk lebih detail.

Dari dokumentasi python 3:

Kode yang memodifikasi koleksi sambil mengulangi koleksi yang sama bisa sulit untuk diperbaiki. Sebagai gantinya, biasanya lebih mudah untuk mengulang salinan koleksi atau membuat koleksi baru:

Iterate melalui salinan

s = {0}
s2 = s.copy()
for i in s2:
     s.add(i + 1)
     s.remove(i)

yang harus diulang hanya 1 kali

>>> print(s)
{1}
>>> print(s2)
{0}

Sunting: Alasan yang mungkin untuk iterasi ini adalah karena satu set tidak berurutan, menyebabkan semacam tumpukan jejak. Jika Anda melakukannya dengan daftar dan bukan satu set, maka itu hanya akan berakhir, dengan s = [1]karena daftar dipesan sehingga perulangan for akan mulai dengan indeks 0 dan kemudian pindah ke indeks berikutnya, menemukan bahwa tidak ada satu, dan keluar dari loop.

Python mengatur koleksi tidak terurut yang tidak merekam posisi elemen atau urutan penyisipan. Tidak ada indeks yang dilampirkan ke elemen apa pun di set python. Jadi mereka tidak mendukung operasi pengindeksan atau pengiris.

Jadi jangan berharap loop for Anda akan bekerja dalam urutan yang ditentukan.

Mengapa ia melakukan 16 iterasi?

user2357112 supports Monicasudah menjelaskan penyebab utamanya. Di sini, ada cara berpikir lain.

s = {0}
for i in s:
     s.add(i + 1)
     print(s)
     s.remove(i)
print(s)

Ketika Anda menjalankan kode ini memberi Anda output ini:

{0, 1}                                                                                                                               
{1, 2}                                                                                                                               
{2, 3}                                                                                                                               
{3, 4}                                                                                                                               
{4, 5}                                                                                                                               
{5, 6}                                                                                                                               
{6, 7}                                                                                                                               
{7, 8}
{8, 9}                                                                                                                               
{9, 10}                                                                                                                              
{10, 11}                                                                                                                             
{11, 12}                                                                                                                             
{12, 13}                                                                                                                             
{13, 14}                                                                                                                             
{14, 15}                                                                                                                             
{16, 15}                                                                                                                             
{16}       

Ketika kita mengakses semua elemen bersama-sama seperti loop atau mencetak set, harus ada urutan yang telah ditetapkan untuk melintasi seluruh set. Jadi, dalam iterasi terakhir Anda akan melihat pesanan diubah seperti dari {i,i+1}menjadi{i+1,i} .

Setelah iterasi terakhir terjadi bahwa i+1sudah dilalui sehingga loop keluar.

Fakta Menarik: Gunakan nilai apa pun yang kurang dari 16 kecuali 6 dan 7 akan selalu memberi Anda hasil 16.