Apakah kamus dipesan dengan Python 3.6+?

469

Kamus diperintahkan dalam Python 3.6 (di bawah implementasi CPython setidaknya) tidak seperti dalam inkarnasi sebelumnya. Ini sepertinya perubahan besar, tetapi hanya paragraf pendek dalam dokumentasi . Ini digambarkan sebagai detail implementasi CPython daripada fitur bahasa, tetapi juga menyiratkan ini dapat menjadi standar di masa depan.

Bagaimana kinerja implementasi kamus baru lebih baik daripada yang lama sambil mempertahankan urutan elemen?

Ini adalah teks dari dokumentasi:

dict()sekarang menggunakan representasi "kompak" yang dipelopori oleh PyPy . Penggunaan memori dict baru () adalah antara 20% dan 25% lebih kecil dibandingkan dengan Python 3.5. PEP 468 (Mempertahankan urutan ** kwargs dalam suatu fungsi.) Diimplementasikan oleh ini. Aspek pelestarian pesanan dari implementasi baru ini dianggap sebagai detail implementasi dan tidak boleh diandalkan (ini dapat berubah di masa depan, tetapi diharapkan memiliki implementasi dict baru ini dalam bahasa untuk beberapa rilis sebelum mengubah spesifikasi bahasa untuk mengamanatkan semantik pengawet pesanan untuk semua implementasi Python saat ini dan di masa depan, ini juga membantu menjaga kompatibilitas ke belakang dengan versi bahasa yang lebih lama di mana urutan iterasi acak masih berlaku, misalnya Python 3.5). (Disumbangkan oleh INADA Naoki dimasalah 27350 . Ide awalnya disarankan oleh Raymond Hettinger .)

Pembaruan Desember 2017: dictpesanan penyisipan penahan dijamin untuk Python 3.7

Chris_Rands
sumber
2
Lihat utas ini di milis Python-Dev: mail.python.org/pipermail/python-dev/2016-September/146327.html jika Anda belum melihatnya; pada dasarnya ini adalah diskusi di sekitar mata pelajaran ini.
mgc
1
Jika kwarg sekarang seharusnya dipesan (yang merupakan ide bagus) dan kwarg adalah dict, bukan OrderedDict, maka saya kira orang bisa berasumsi bahwa kunci dict akan tetap dipesan di versi Python yang akan datang, meskipun dokumentasi mengatakan sebaliknya.
Dmitriy Sintsov
4
@ DmitriySintsov Tidak, jangan membuat asumsi itu. Ini adalah masalah yang diangkat selama penulisan PEP yang mendefinisikan fitur pelestarian pesanan **kwargsdan karena itu kata-kata yang digunakan adalah diplomatik: **kwargsdalam suatu fungsi tanda tangan sekarang dijamin menjadi pemetaan pelestarian urutan-penyisipan . Mereka telah menggunakan istilah pemetaan untuk tidak memaksa implementasi lain untuk membuat diktat dipesan (dan menggunakan OrderedDictinternal) dan sebagai cara untuk memberi sinyal bahwa ini tidak seharusnya tergantung pada kenyataan bahwa dicttidak dipesan.
Dimitris Fasarakis Hilliard
7
Penjelasan video yang bagus dari Raymond Hettinger
Alex
1
@wazoox, urutan dan kompleksitas dari hashmap tidak berubah. Perubahan itu membuat hashmap lebih kecil dengan membuang lebih sedikit ruang, dan ruang yang disimpan (biasanya?) Lebih dari yang dibutuhkan array bantu. Lebih cepat, lebih kecil, dipesan - Anda harus memilih semua 3.
John La Rooy

Jawaban:

512

Apakah kamus dipesan dengan Python 3.6+?

Mereka memerintahkan penyisipan [1] . Pada Python 3.6, untuk implementasi Python CPython, kamus mengingat urutan item yang dimasukkan . Ini dianggap sebagai detail implementasi dalam Python 3.6 ; Anda perlu menggunakan OrderedDictjika Anda ingin pemesanan penyisipan yang dijamin di seluruh implementasi Python lainnya (dan perilaku berurutan lainnya [1] ).

Pada Python 3.7 , ini bukan lagi detail implementasi dan malah menjadi fitur bahasa. Dari pesan python-dev oleh GvR :

Jadikan begitu. "Dict menjaga urutan penyisipan" adalah putusannya. Terima kasih!

Ini berarti bahwa Anda dapat bergantung padanya . Implementasi lain dari Python juga harus menawarkan penyisipan kamus jika mereka ingin menjadi implementasi yang sesuai dari Python 3.7.


Bagaimana 3.6implementasi kamus Python berkinerja lebih baik [2] dari yang sebelumnya sambil mempertahankan urutan elemen?

Intinya, dengan menjaga dua array .

  • Array pertama dk_entries,, menampung entri ( dari jenisPyDictKeyEntry ) untuk kamus sesuai urutan yang dimasukkan. Order pelestarian dicapai dengan menjadi array append saja di mana item baru selalu disisipkan di akhir (urutan penyisipan).

  • Yang kedua,, dk_indicesmemegang indeks untuk dk_entriesarray (yaitu, nilai-nilai yang menunjukkan posisi entri yang sesuai di dk_entries). Array ini bertindak sebagai tabel hash. Ketika kunci di-hash, itu mengarah ke salah satu indeks yang disimpan dk_indicesdan entri yang sesuai diambil dengan mengindeks dk_entries. Karena hanya indeks yang disimpan, jenis larik ini tergantung pada ukuran keseluruhan kamus (mulai dari jenis int8_t( 1byte) hingga int32_t/ int64_t( 4/ 8byte) di 32/ 64bit builds)

Dalam implementasi sebelumnya, berbagai jenis PyDictKeyEntrydan ukuran dk_sizeharus dialokasikan; Sayangnya, itu juga menghasilkan banyak ruang kosong karena array itu tidak boleh lebih dari 2/3 * dk_sizepenuh karena alasan kinerja . (dan ruang kosong masih memiliki PyDictKeyEntryukuran!).

Ini bukan masalahnya sekarang karena hanya entri yang diperlukan yang disimpan (yang telah dimasukkan) dan jenis array yang jarang intX_t( Xtergantung pada ukuran dict) 2/3 * dk_sizepenuh disimpan. Ruang kosong berubah dari tipe PyDictKeyEntryke intX_t.

Jadi, jelas, membuat array tipe jarang PyDictKeyEntryjauh lebih banyak menuntut memori daripada array jarang untuk menyimpan ints.

Anda dapat melihat percakapan lengkap di Python-Dev mengenai fitur ini jika tertarik, ini adalah bacaan yang bagus.


Dalam proposal asli yang dibuat oleh Raymond Hettinger , visualisasi dari struktur data yang digunakan dapat dilihat yang menangkap inti gagasan.

Misalnya, kamus:

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

saat ini disimpan sebagai [keyhash, key, value]:

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

Sebagai gantinya, data harus disusun sebagai berikut:

indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]

Seperti yang dapat Anda lihat secara visual sekarang, dalam proposal asli, banyak ruang pada dasarnya kosong untuk mengurangi tabrakan dan membuat pencarian lebih cepat. Dengan pendekatan baru, Anda mengurangi memori yang dibutuhkan dengan menggerakkan sparseness di tempat yang benar-benar diperlukan, dalam indeks.


[1]: Saya katakan "penyisipan memerintahkan" dan tidak "memerintahkan" karena, dengan adanya OrderedDict, "memerintahkan" menunjukkan perilaku lebih lanjut bahwa dictobjek tidak menyediakan . OrderedDicts bersifat reversibel, menyediakan metode sensitif pesanan dan, terutama, memberikan tes kesetaraan pesanan-luas ( ==, !=). dictSaat ini tidak menawarkan perilaku / metode tersebut.


[2]: Implementasi kamus baru menghasilkan ingatan yang lebih baik dengan dirancang lebih kompak; itulah manfaat utama di sini. Dari segi kecepatan, perbedaannya tidak terlalu drastis, ada tempat-tempat dict yang baru mungkin memperkenalkan sedikit kemunduran ( pencarian kunci, misalnya ) sementara di tempat lain (iterasi dan mengubah ukuran muncul dalam pikiran) peningkatan kinerja harus ada.

Secara keseluruhan, kinerja kamus, terutama dalam situasi kehidupan nyata, meningkat karena kekompakan yang diperkenalkan.

Dimitris Fasarakis Hilliard
sumber
15
Jadi, apa yang terjadi ketika suatu barang dihapus? Apakah entriesdaftar diubah ukurannya? atau ruang kosong disimpan? atau dikompresi dari waktu ke waktu?
njzk2
18
@ njzk2 Ketika item dihapus, indeks yang sesuai digantikan oleh DKIX_DUMMYdengan nilai -2dan entri dalam entryarray digantikan olehNULL , ketika memasukkan dilakukan nilai-nilai baru ditambahkan ke array entri, Belum bisa melihat, tapi cukup yakin ketika indeks terisi melebihi 2/3ambang batas dilakukan. Ini dapat menyebabkan penyusutan alih-alih bertambah jika banyak DUMMYentri.
Dimitris Fasarakis Hilliard
3
@ Chris_Rands Tidak, satu-satunya regresi aktual yang saya lihat adalah pada pelacak di a pesan oleh Victor . Selain microbenchmark itu, saya tidak melihat ada masalah / pesan lain yang menunjukkan perbedaan kecepatan yang serius dalam beban kerja di kehidupan nyata. Ada tempat di mana dikte baru mungkin memperkenalkan sedikit regresi (pencarian kunci, misalnya) sementara di tempat lain (iterasi dan mengubah ukuran muncul di benak) peningkatan kinerja akan hadir.
Dimitris Fasarakis Hilliard
3
Koreksi pada bagian pengubahan ukuran : Kamus tidak mengubah ukuran ketika Anda menghapus item, mereka menghitung ulang ketika Anda memasukkan kembali. Jadi, jika sebuah dikt dibuat dengan d = {i:i for i in range(100)}dan Anda .popsemua item tanpa memasukkan, ukurannya tidak akan berubah. Ketika Anda menambahkannya lagi, d[1] = 1ukuran yang sesuai dihitung dan ukurannya diubah.
Dimitris Fasarakis Hilliard
6
@Chris_Rands Saya cukup yakin itu tetap. Masalahnya adalah, dan alasan mengapa saya mengubah jawaban saya untuk menghapus pernyataan selimut tentang ' dictdipesan', dicts tidak dipesan dalam arti OrderedDicts. Masalah yang menonjol adalah kesetaraan. dictAda pesanan tidak sensitif ==, OrderedDictada pesanan sensitif. Membuang OrderedDictdan mengubah dictsuntuk sekarang memiliki perbandingan sensitif urutan dapat menyebabkan banyak kerusakan pada kode lama. Saya menduga satu-satunya hal yang mungkin berubah tentang OrderedDicts adalah implementasinya.
Dimitris Fasarakis Hilliard
67

Di bawah ini menjawab pertanyaan pertama yang asli:

Haruskah saya gunakan dict atau OrderedDictdengan Python 3.6?

Saya pikir kalimat dari dokumentasi ini sebenarnya cukup untuk menjawab pertanyaan Anda

Aspek pelestarian pesanan dari implementasi baru ini dianggap sebagai detail implementasi dan tidak dapat diandalkan

dicttidak secara eksplisit dimaksudkan sebagai koleksi yang dipesan, jadi jika Anda ingin tetap konsisten dan tidak bergantung pada efek samping dari implementasi baru Anda harus tetap menggunakannya OrderedDict.

Buat kode Anda menjadi bukti di masa depan :)

Ada perdebatan tentang itu di sini .

EDIT: Python 3.7 akan membuat ini sebagai fitur lihat

Maresh
sumber
1
Tampaknya jika mereka tidak bermaksud menjadikannya fitur nyata tetapi hanya detail implementasi maka mereka seharusnya tidak memasukkannya ke dalam dokumentasi.
xji
3
Saya tidak yakin tentang peringatan edit Anda; karena jaminan hanya berlaku untuk Python 3.7, saya berasumsi saran untuk Python 3.6 tidak berubah, yaitu dicts dipesan dalam CPython tetapi jangan mengandalkannya
Chris_Rands
25

Pembaruan: Guido van Rossum mengumumkan di milis bahwa pada Python 3.7 dicts di semua implementasi Python harus mempertahankan urutan penyisipan.

fjsj
sumber
2
Sekarang pemesanan utama adalah standar resmi, apa tujuan dari OrderedDict? Atau, apakah sekarang berlebihan?
Jonny Waffles
2
Saya kira OrderedDict tidak akan berlebihan karena memiliki move_to_endmetode dan kesetaraannya peka terhadap pesanan: docs.python.org/3/library/… . Lihat catatan pada jawaban Jim Fasarakis Hilliard.
fjsj
@JonnyWaffles lihat jawaban Jim dan Q&A ini stackoverflow.com/questions/50872498/…
Chris_Rands
3
Jika Anda ingin kode Anda menjalankan hal yang sama pada 2.7 dan 3.6 / 3.7 +, Anda harus menggunakan OrderedDict
boatcoder
3
Kemungkinan akan ada "UnorderedDict" segera untuk orang-orang yang suka repot dicts mereka karena alasan keamanan; p
ZF007
9

Saya ingin menambah diskusi di atas tetapi tidak memiliki reputasi untuk berkomentar.

Python 3.8 belum cukup dirilis, tetapi bahkan akan menyertakan reversed()fungsi pada kamus (menghapus perbedaan lain dari OrderedDict.

Diktik dan dictviews sekarang dapat diubah dalam urutan penyisipan terbalik menggunakan reversed (). (Dikontribusikan oleh Rémi Lapeyre di bpo-33462.) Lihat apa yang baru dengan python 3.8

Saya tidak melihat penyebutan operator kesetaraan atau fitur lain OrderedDictsehingga mereka masih belum sepenuhnya sama.

rkengler
sumber