Saya terkejut menemukan baru-baru ini bahwa sementara dikt dijamin untuk menjaga urutan penyisipan dengan Python 3.7+, set tidak:
>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> d
{'a': 1, 'b': 2, 'c': 3}
>>> d['d'] = 4
>>> d
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
>>> s = {'a', 'b', 'c'}
>>> s
{'b', 'a', 'c'}
>>> s.add('d')
>>> s
{'d', 'b', 'a', 'c'}
Apa alasan untuk perbedaan ini? Apakah peningkatan efisiensi yang sama yang menyebabkan tim Python mengubah implementasi dikt tidak berlaku untuk set juga?
Saya tidak mencari petunjuk untuk implementasi yang dipesan-set atau cara untuk menggunakan dikt sebagai stand-in untuk set. Saya hanya ingin tahu mengapa tim Python tidak membuat set built-in menjaga ketertiban pada saat yang sama mereka melakukannya untuk dikte.
dict
danset
sejak 2.7.Jawaban:
Perangkat dan dikte dioptimalkan untuk berbagai kasus penggunaan. Penggunaan utama dari set adalah pengujian keanggotaan cepat, yang merupakan pesanan agnostik.Untuk dicts, biaya pencarian adalah operasi yang paling kritis, dan kuncinya lebih mungkin ada. Dengan set, ada atau tidaknya elemen tidak diketahui sebelumnya, dan implementasi set perlu dioptimalkan untuk kasus yang ditemukan dan tidak ditemukan. Juga, beberapa optimisasi untuk operasi himpunan umum seperti union dan persimpangan membuat sulit untuk mempertahankan pemesanan himpunan tanpa menurunkan kinerja.
Sementara kedua struktur data berdasarkan hash, itu adalah kesalahpahaman umum bahwa set hanya diimplementasikan sebagai dikts dengan nilai nol. Bahkan sebelum implementasi dict kompak dalam CPython 3.6, implementasi set dan dict sudah berbeda secara signifikan, dengan sedikit kode yang digunakan kembali. Misalnya, dicts menggunakan probing acak, tetapi set menggunakan kombinasi linear probing dan open addressing, untuk meningkatkan lokalitas cache. Probe linear awal (default 9 langkah dalam CPython) akan memeriksa serangkaian pasangan kunci / hash yang berdekatan, meningkatkan kinerja dengan mengurangi biaya penanganan benturan hash - akses memori berturut-turut lebih murah daripada probe yang tersebar.
dictobject.c
- master , v3.5.9setobject.c
- master , v3.5.9Secara teori dimungkinkan untuk mengubah implementasi himpunan CPython menjadi serupa dengan dikt kompak, tetapi dalam praktiknya ada kelemahan, dan pengembang inti terkenal menentang untuk melakukan perubahan semacam itu.
- Guido van Rossum
- Raymond Hettinger
Diskusi terperinci tentang apakah akan memadatkan set untuk 3.7, dan jawaban tentang mengapa diputuskan menentang, dapat ditemukan di milis python-dev.
Singkatnya, poin utama adalah bahwa pola penggunaannya berbeda (perintah pemesanan penyisipan seperti ** kwarg berguna , kurang begitu untuk set), penghematan ruang untuk set compacting kurang signifikan (karena hanya ada kunci dan array hash untuk densifikasi, tidak seperti kunci, hash dan nilai), dan optimisasi probing linier dalam set tidak sesuai dengan implementasi yang kompak.
Saya akan mereproduksi posting Raymond di bawah ini yang mencakup poin paling penting.
Dari [Python-Dev] Python 3.6 dict menjadi ringkas dan mendapatkan versi pribadi; dan kata kunci dipesan , September 2016.
sumber
Diskusi
Pertanyaan Anda erat dan sudah banyak dibahas di python-devs belum lama ini. R. Hettinger membagikan daftar alasan di utas itu . Keadaan masalah sekarang tampak terbuka sekarang, tak lama setelah jawaban rinci dari T. Peters ini.
Singkatnya, penerapan dikte modern yang mempertahankan urutan penyisipan adalah unik dan tidak dianggap sesuai dengan set. Secara khusus, dikt digunakan di mana-mana untuk menjalankan Python (misalnya
__dict__
dalam ruang nama objek). Motivasi utama di balik dikte modern adalah untuk mengurangi ukuran, membuat Python lebih efisien secara keseluruhan. Sebaliknya, set kurang umum daripada dikte dalam inti Python dan dengan demikian menghalangi refactoring tersebut. Lihat juga pembicaraan R. Hettinger tentang implementasi dikt modern.Perspektif
Sifat unordered set dalam Python sejajar dengan perilaku set matematika . Pesanan tidak dijamin.
Jika urutan apa pun diperkenalkan ke set dengan Python, maka perilaku ini akan sesuai dengan struktur matematika yang benar-benar terpisah, yaitu set yang dipesan (atau Oset). Osets memainkan peran yang terpisah dalam matematika, khususnya dalam kombinatorik. Salah satu aplikasi praktis Osets diamati dalam perubahan bel .
Memiliki set unordered konsisten dengan struktur data yang sangat generik dan di mana-mana yang membuka pin kebanyakan matematika modern, yaitu Set Theory . Saya serahkan, set unordered dengan Python baik untuk dimiliki.
Lihat juga posting terkait yang memperluas topik ini:
sumber