Mengapa urutan dalam kamus dan ditetapkan sewenang-wenang?

Saya tidak mengerti bagaimana perulangan kamus atau diatur dengan python dilakukan dengan urutan 'sewenang-wenang'.

Maksud saya, ini adalah bahasa pemrograman sehingga segala sesuatu dalam bahasa tersebut harus ditentukan 100%, benar? Python harus memiliki beberapa jenis algoritma yang memutuskan bagian mana dari kamus atau set yang dipilih, 1, kedua dan seterusnya.

Apa yang saya lewatkan?

Catatan: Jawaban ini ditulis sebelum implementasi dicttipe diubah, dengan Python 3.6. Sebagian besar detail implementasi dalam jawaban ini masih berlaku, tetapi urutan listing kunci dalam kamus tidak lagi ditentukan oleh nilai hash. Implementasi yang ditetapkan tetap tidak berubah.

Urutannya tidak sewenang-wenang, tetapi tergantung pada penyisipan dan penghapusan riwayat kamus atau set, serta pada implementasi Python tertentu. Untuk sisa jawaban ini, untuk 'kamus', Anda juga dapat membaca 'set'; set diimplementasikan sebagai kamus dengan kunci adil dan tanpa nilai.

Kunci hash, dan nilai hash ditugaskan ke slot di tabel dinamis (dapat tumbuh atau menyusut berdasarkan kebutuhan). Dan proses pemetaan itu dapat menyebabkan tabrakan, yang berarti bahwa sebuah kunci harus ditempatkan di slot berikutnya berdasarkan apa yang sudah ada.

Daftar loop konten di atas slot, dan kunci terdaftar dalam urutan saat ini berada di tabel.

Ambil kunci 'foo'dan 'bar', misalnya, dan mari kita asumsikan ukuran tabel adalah 8 slot. Dalam Python 2.7, hash('foo')is -4177197833195190597, hash('bar')is 327024216814240868. Modulo 8, itu berarti dua tombol ini ditempatkan di slot 3 dan 4 lalu:

>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4

Ini menginformasikan pesanan listing mereka:

>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}

Semua slot kecuali 3 dan 4 kosong, looping di atas meja pertama daftar slot 3, lalu slot 4, jadi 'foo'terdaftar sebelumnya 'bar'.

bardan baz, bagaimanapun, memiliki nilai hash yang persis 8 terpisah dan dengan demikian peta ke slot yang sama persis, 4:

>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4

Pesanan mereka sekarang tergantung pada kunci mana yang ditempatkan pertama kali; tombol kedua harus dipindahkan ke slot berikutnya:

>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}

Urutan tabel berbeda di sini, karena salah satu atau kunci lainnya ditempatkan terlebih dahulu.

Nama teknis untuk struktur dasar yang digunakan oleh CPython (implementasi Python yang paling umum digunakan) adalah tabel hash , yang menggunakan pengalamatan terbuka. Jika Anda penasaran, dan memahami C dengan cukup baik, lihat implementasi C untuk semua detail (terdokumentasi dengan baik). Anda juga dapat menonton presentasi Pycon 2010 ini oleh Brandon Rhodes tentang cara dictkerja CPython , atau mengambil salinan Kode Cantik , yang mencakup bab tentang implementasi yang ditulis oleh Andrew Kuchling.

Perhatikan bahwa pada Python 3.3, benih hash acak juga digunakan, membuat tabrakan hash tidak dapat diprediksi untuk mencegah beberapa jenis penolakan layanan (di mana seorang penyerang membuat server Python tidak responsif dengan menyebabkan benturan hash massal). Ini berarti bahwa urutan kamus atau set yang diberikan kemudian juga tergantung pada seed hash acak untuk permintaan Python saat ini.

Implementasi lain bebas menggunakan struktur berbeda untuk kamus, asalkan memenuhi antarmuka Python yang terdokumentasi untuk mereka, tapi saya percaya bahwa semua implementasi sejauh ini menggunakan variasi dari tabel hash.

CPython 3.6 memperkenalkan baru dict implementasi yang mempertahankan urutan penyisipan, dan lebih cepat dan lebih efisien untuk mem-boot. Daripada menyimpan tabel jarang yang besar di mana setiap baris mereferensikan nilai hash yang tersimpan, dan objek kunci dan nilai, implementasi baru menambahkan array hash yang lebih kecil yang hanya mereferensikan indeks dalam tabel 'padat' yang terpisah (yang hanya berisi banyak baris karena ada pasangan nilai kunci yang sebenarnya), dan itu adalah tabel padat yang terjadi untuk mendaftar item yang ada dalam urutan. Lihat proposal ke Python-Dev untuk lebih jelasnya . Perhatikan bahwa dalam Python 3.6 ini dianggap sebagai detail implementasi, Python-the-language tidak menentukan bahwa implementasi lain harus mempertahankan ketertiban. Ini berubah dalam Python 3.7, di mana detail ini dinaikkan menjadi spesifikasi bahasa ; untuk implementasi apa pun agar kompatibel dengan Python 3.7 atau yang lebih baru, harus menyalin perilaku mempertahankan pesanan ini. Dan untuk menjadi eksplisit: perubahan ini tidak berlaku untuk set, karena set sudah memiliki struktur hash 'kecil'.

Python 2.7 dan yang lebih baru juga menyediakan OrderedDictkelas , subkelas dictyang menambahkan struktur data tambahan untuk merekam urutan kunci. Dengan harga beberapa kecepatan dan memori tambahan, kelas ini mengingat bagaimana Anda memasukkan kunci; daftar kunci, nilai, atau item kemudian akan melakukannya dalam urutan itu. Ini menggunakan daftar tertaut ganda yang disimpan dalam kamus tambahan untuk menjaga agar pesanan selalu diperbarui secara efisien. Lihat posting Raymond Hettinger yang menguraikan gagasan itu . OrderedDictbenda memiliki kelebihan lain, seperti dipesan ulang .

Jika Anda menginginkan set yang dipesan, Anda dapat menginstal osetpaket ; ini bekerja pada Python 2.5 dan lebih tinggi.

Ini lebih merupakan respons terhadap Python 3.41 Satu set sebelum ditutup sebagai duplikat.

Yang lain benar: jangan mengandalkan pesanan. Jangan pura-pura ada.

Yang mengatakan, ada satu hal yang dapat Anda andalkan:

list(myset) == list(myset)

Artinya, pesanannya stabil .

Memahami mengapa ada tatanan yang dirasakan membutuhkan pemahaman beberapa hal:

• Python itu menggunakan hash set ,

• Bagaimana set hash CPython disimpan dalam memori dan

• Bagaimana angka di-hash

Dari atas:

Sebuah set hash adalah metode menyimpan data acak dengan waktu sangat cepat lookup.

Ini memiliki array dukungan:

# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6

Kami akan mengabaikan objek boneka khusus, yang ada hanya untuk membuat penghapusan lebih mudah untuk ditangani, karena kami tidak akan menghapus dari set ini.

Untuk mendapatkan pencarian yang sangat cepat, Anda melakukan sihir untuk menghitung hash dari suatu objek. Satu-satunya aturan adalah bahwa dua objek yang sama memiliki hash yang sama. (Tetapi jika dua objek memiliki hash yang sama, mereka bisa tidak sama.)

Anda kemudian membuat indeks dengan mengambil modulus oleh panjang array:

hash(4) % len(storage) = index 2

Ini membuatnya sangat cepat untuk mengakses elemen.

Hash hanya sebagian besar cerita, karena hash(n) % len(storage)dan hash(m) % len(storage)dapat menghasilkan jumlah yang sama. Dalam hal ini, beberapa strategi berbeda dapat mencoba dan menyelesaikan konflik. CPython menggunakan "linear probing" 9 kali sebelum melakukan hal-hal yang rumit, sehingga akan terlihat di sebelah kiri slot hingga 9 tempat sebelum mencari di tempat lain.

Kumpulan hash CPython disimpan seperti ini:

• Kumpulan hash tidak boleh lebih dari 2/3 penuh . Jika ada 20 elemen dan panjang array 30 elemen, toko dukungan akan diubah ukurannya menjadi lebih besar. Ini karena Anda lebih sering bertabrakan dengan toko dukungan kecil, dan tabrakan memperlambat semuanya.

• Toko dukungan ukuran dalam kekuatan 4, mulai dari 8, kecuali untuk set besar (elemen 50k) yang mengubah ukuran dalam kekuatan dua: (8, 32, 128, ...).

Jadi ketika Anda membuat sebuah array, backing store adalah panjang 8. Ketika 5 penuh dan Anda menambahkan elemen, itu akan secara singkat berisi 6 elemen. 6 > ²⁄₃·8jadi ini memicu pengubahan ukuran, dan backing store empat kali lipat ke ukuran 32.

Akhirnya, hash(n)hanya mengembalikan nangka (kecuali -1yang khusus).

Jadi, mari kita lihat yang pertama:

v_set = {88,11,1,33,21,3,7,55,37,8}

len(v_set)adalah 10, jadi backing store setidaknya 15 (+1) setelah semua item ditambahkan . Kekuatan yang relevan dari 2 adalah 32. Jadi toko dukungan adalah:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

Kita punya

hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1)  % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3)  % 32 = 3
hash(7)  % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8)  % 32 = 8

jadi masukkan ini sebagai:

__  1 __  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
   33 ← Can't also be where 1 is;
        either 1 or 33 has to move

Jadi kami akan mengharapkan pesanan seperti

{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}

dengan 1 atau 33 yang tidak di mulai di tempat lain. Ini akan menggunakan linear probing, jadi kita akan memiliki:

       ↓
__  1 33  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

atau

       ↓
__ 33  1  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

Anda mungkin berharap 33 menjadi salah satu yang dipindahkan karena 1 sudah ada di sana, tetapi karena ukuran yang terjadi saat set sedang dibangun, ini sebenarnya tidak terjadi. Setiap kali set dibangun kembali, item yang sudah ditambahkan akan disusun ulang secara efektif.

Sekarang Anda bisa melihat alasannya

{7,5,11,1,4,13,55,12,2,3,6,20,9,10}

mungkin dalam rangka. Ada 14 elemen, jadi backing store setidaknya 21 + 1, yang berarti 32:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

1 hingga 13 hash di 13 slot pertama. 20 masuk dalam slot 20.

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __

55 masuk dalam slot hash(55) % 32yaitu 23:

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __

Jika kami memilih 50 sebagai gantinya, kami harapkan

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __

Dan lihatlah:

{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
#>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}

pop diimplementasikan dengan cukup sederhana oleh hal-hal yang terlihat: itu melintasi daftar dan muncul yang pertama.

Ini semua detail implementasi.

"Sewenang-wenang" tidak sama dengan "tidak ditentukan".

Apa yang mereka katakan adalah bahwa tidak ada properti yang berguna dari urutan iterasi kamus yang "di antarmuka publik". Hampir pasti ada banyak properti dari urutan iterasi yang sepenuhnya ditentukan oleh kode yang saat ini mengimplementasikan iterasi kamus, tetapi penulis tidak menjanjikannya kepada Anda sebagai sesuatu yang dapat Anda gunakan. Ini memberi mereka lebih banyak kebebasan untuk mengubah properti ini antara versi Python (atau bahkan hanya dalam kondisi operasi yang berbeda, atau sepenuhnya secara acak saat runtime) tanpa khawatir bahwa program Anda akan rusak.

Jadi, jika Anda menulis program yang bergantung pada properti apa pun di semua urutan kamus, maka Anda "melanggar kontrak" menggunakan jenis kamus, dan pengembang Python tidak menjanjikan bahwa ini akan selalu bekerja, bahkan jika itu tampaknya bekerja untuk saat ini ketika Anda mengujinya. Ini pada dasarnya sama dengan mengandalkan "perilaku tidak terdefinisi" dalam C.

Jawaban lain untuk pertanyaan ini sangat bagus dan ditulis dengan baik. OP bertanya "bagaimana" yang saya artikan sebagai "bagaimana mereka lolos" atau "mengapa".

Dokumentasi Python mengatakan kamus tidak dipesan karena kamus Python mengimplementasikan array asosiatif tipe data abstrak . Seperti yang mereka katakan

urutan pengikatan dikembalikan mungkin sewenang-wenang

Dengan kata lain, seorang siswa ilmu komputer tidak dapat berasumsi bahwa array asosiatif dipesan. Hal yang sama berlaku untuk set dalam matematika

urutan unsur-unsur himpunan terdaftar tidak relevan

dan ilmu komputer

set adalah tipe data abstrak yang dapat menyimpan nilai-nilai tertentu, tanpa urutan tertentu

Menerapkan kamus menggunakan tabel hash adalah detail implementasi yang menarik karena memiliki sifat yang sama dengan array asosiatif sejauh menyangkut urutan.

Python menggunakan tabel hash untuk menyimpan kamus, sehingga tidak ada urutan dalam kamus atau objek iterable lainnya yang menggunakan tabel hash.

Tetapi mengenai indeks item dalam objek hash, python menghitung indeks berdasarkan kode berikut dalamhashtable.c :

key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);

Oleh karena itu, karena nilai hash bilangan bulat adalah bilangan bulat itu sendiri ^* indeks didasarkan pada angka ( ht->num_buckets - 1adalah konstanta) sehingga indeks dihitung oleh Bitwise-dan di antara (ht->num_buckets - 1)dan angka itu sendiri ^* (berharap untuk -1 yang hashnya adalah -2 ), dan untuk objek lain dengan nilai hash mereka.

pertimbangkan contoh berikut dengan setmenggunakan hash-table:

>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])

Untuk nomor yang 33kami miliki:

33 & (ht->num_buckets - 1) = 1

Sebenarnya itu:

'0b100001' & '0b111'= '0b1' # 1 the index of 33

Catatan dalam hal ini (ht->num_buckets - 1)adalah 8-1=7atau 0b111.

Dan untuk 1919:

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919

Dan untuk 333:

'0b101001101' & '0b111' = '0b101' # 5 the index of 333

Untuk detail lebih lanjut tentang fungsi hash python ada baiknya untuk membaca kutipan berikut dari kode sumber python :

Kehalusan utama di depan: Sebagian besar skema hash bergantung pada memiliki fungsi hash "baik", dalam arti mensimulasikan keacakan. Python tidak: fungsi hash yang paling penting (untuk string dan int) sangat umum dalam kasus-kasus umum:

>>> map(hash, (0, 1, 2, 3))
  [0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
  [-1658398457, -1658398460, -1658398459, -1658398462]

Ini tidak selalu buruk! Sebaliknya, dalam tabel ukuran 2 ** i, mengambil bit orde rendah karena indeks tabel awal sangat cepat, dan tidak ada tabrakan sama sekali untuk dicts yang diindeks oleh kisaran int yang berdekatan. Hal yang sama kira-kira benar ketika kunci adalah string "berurutan". Jadi ini memberikan perilaku yang lebih baik daripada acak dalam kasus-kasus umum, dan itu sangat diinginkan.

OTOH, ketika tabrakan terjadi, kecenderungan untuk mengisi irisan tabel hash yang berdekatan membuat strategi resolusi tabrakan yang baik menjadi penting. Mengambil hanya bit i terakhir dari kode hash juga rentan: misalnya, pertimbangkan daftar [i << 16 for i in range(20000)]sebagai seperangkat kunci. Karena int adalah kode hash mereka sendiri, dan ini cocok dengan dict ukuran 2 ** 15, 15 bit terakhir dari setiap kode hash semuanya 0: mereka semua peta ke indeks tabel yang sama.

Tetapi melayani kasus-kasus yang tidak biasa seharusnya tidak memperlambat yang biasa, jadi kami mengambil bit terakhir. Terserah resolusi tabrakan untuk melakukan sisanya. Jika kita biasanya menemukan kunci yang kita cari pada percobaan pertama (dan, ternyata, biasanya kita lakukan - faktor muatan tabel disimpan di bawah 2/3, jadi kemungkinannya sangat menguntungkan kita), maka itu masuk akal untuk menjaga agar indeks perhitungan awal tetap murah.

_{* Fungsi hash untuk kelas int:}

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value = -2
        return value

Dimulai dengan Python 3.7 (dan sudah ada di CPython 3.6 ), item kamus tetap dalam urutan mereka dimasukkan .