Bagaimana set () diimplementasikan?

151

Saya telah melihat orang mengatakan bahwa setobjek dalam python memiliki O (1) pengecekan keanggotaan. Bagaimana mereka diterapkan secara internal untuk memungkinkan ini? Jenis struktur data apa yang digunakannya? Apa implikasi lain yang dimiliki implementasi itu?

Setiap jawaban di sini benar-benar mencerahkan, tetapi saya hanya bisa menerimanya, jadi saya akan mencari jawaban terdekat dengan pertanyaan awal saya. Terima kasih atas informasinya!

python data-structures set cpython Daenyth
sumber

Jawaban:

139

Menurut utas ini :

Memang, set CPython diimplementasikan sebagai sesuatu seperti kamus dengan nilai-nilai dummy (kunci menjadi anggota set), dengan beberapa optimasi yang mengeksploitasi kurangnya nilai-nilai ini

Jadi pada dasarnya a setmenggunakan hashtable sebagai struktur datanya. Ini menjelaskan O (1) yang memeriksa keanggotaan, karena mencari item dalam hashtable adalah operasi O (1), rata-rata.

Jika Anda cenderung, Anda bahkan dapat menelusuri kode sumber CPython untuk set yang, menurut Achim Domma , sebagian besar merupakan cut-and-paste dari dictimplementasi.

Justin Ethier
sumber
18
IIRC, asli setpelaksanaan sebenarnya adalah dict dengan nilai-nilai boneka, dan itu bisa dioptimalkan kemudian.
dan04
1
Bukankah besar O skenario terburuk? Jika Anda dapat menemukan contoh di mana waktunya adalah O (n) maka itu adalah O (n) .. Saya tidak mengerti apa-apa sekarang dari semua tutorial itu.
Claudiu Creanga
4
Tidak, kasus rata-rata adalah O (1) tetapi kasus terburuk adalah O (N) untuk pencarian tabel hash.
Justin Ethier
4
@ClaudiuCreanga ini adalah komentar lama, tetapi hanya untuk memperjelas: notasi O besar memberi tahu Anda batas atas pada tingkat pertumbuhan hal-hal, tetapi Anda dapat membatasi pertumbuhan kinerja kasus rata-rata dan Anda dapat secara terpisah mengikat pertumbuhan kasus terburuk kinerja.
Kirk Boyer
79

Ketika orang mengatakan set memiliki O (1) memeriksa keanggotaan, mereka berbicara tentang kasus rata - rata . Dalam kasus terburuk (ketika semua nilai hash bertabrakan) pengecekan keanggotaan adalah O (n). Lihat wiki Python pada kompleksitas waktu .

The artikel Wikipedia mengatakan kasus terbaik waktu kompleksitas untuk tabel hash yang tidak resize adalah O(1 + k/n). Hasil ini tidak secara langsung berlaku untuk set Python karena set Python menggunakan tabel hash yang mengubah ukuran.

Sedikit lebih jauh pada artikel Wikipedia mengatakan bahwa untuk kasus rata - rata , dan dengan asumsi fungsi hashing seragam sederhana, kompleksitas waktu adalah O(1/(1-k/n)), di mana k/ndapat dibatasi oleh konstanta c<1.

Big-O hanya merujuk pada perilaku asimptotik sebagai n → ∞. Karena k / n dapat dibatasi oleh konstanta, c <1, tidak bergantung pada n ,

O(1/(1-k/n))tidak lebih besar dari O(1/(1-c))yang setara dengan O(constant)= O(1).

Jadi dengan asumsi hashing sederhana yang seragam, rata-rata , memeriksa keanggotaan untuk set Python adalah O(1).

unutbu
sumber
14

Saya pikir ini adalah kesalahan umum, setpencarian (atau hashtable dalam hal ini) bukan O (1)
dari Wikipedia

Dalam model paling sederhana, fungsi hash sepenuhnya tidak ditentukan dan tabel tidak mengubah ukuran. Untuk pilihan fungsi hash terbaik, tabel ukuran n dengan pengalamatan terbuka tidak memiliki tabrakan dan menampung hingga n elemen, dengan satu perbandingan untuk pencarian sukses, dan tabel ukuran n dengan rantai dan kunci k memiliki maksimum minimum (0, kn) tabrakan dan perbandingan O (1 + k / n) untuk pencarian. Untuk pilihan fungsi hash terburuk, setiap penyisipan menyebabkan tabrakan, dan tabel hash berubah menjadi pencarian linier, dengan perbandingan diamortisasi Ω (k) per penyisipan dan hingga perbandingan k untuk pencarian sukses.

Terkait: Apakah Java hashmap benar-benar O (1)?

Shay Erlichmen
sumber
4
Tetapi mereka membutuhkan waktu konstan untuk mencari item: python -m timeit -s "s = set (range (10))" "5 in s" 10000000 loop, terbaik dari 3: 0,0642 usec per loop <--> python - m timeit -s "s = set (range (10000000))" "5 in s" 10000000 loop, terbaik dari 3: 0,0634 usec per loop ... dan itulah set terbesar yang tidak melempar MemoryErrors
Jochen Ritzel
2
@ THC4k Semua yang Anda buktikan adalah bahwa mencari X dilakukan dalam waktu yang konstan, tetapi itu tidak berarti bahwa waktu untuk mencari X + Y akan membutuhkan jumlah waktu yang sama dengan O (1).
Shay Erlichmen
3
@intuited: Memang, tetapi tes yang dijalankan di atas tidak membuktikan bahwa Anda dapat melihat "5" pada saat yang sama Anda dapat mencari "485398", atau nomor lain yang mungkin berada di ruang tabrakan yang mengerikan. Ini bukan tentang mencari elemen yang sama dalam hash berukuran berbeda dalam waktu yang sama (pada kenyataannya, itu tidak diperlukan sama sekali), melainkan tentang apakah Anda dapat mengakses setiap entri dalam jumlah waktu yang sama dalam tabel saat ini - sesuatu yang pada dasarnya tidak mungkin dicapai oleh tabel hash karena umumnya akan selalu ada tabrakan.
Nick Bastin
3
Dengan kata lain, waktu untuk melakukan pencarian tergantung pada jumlah nilai yang disimpan, karena itu meningkatkan kemungkinan tabrakan.
intuited
3
@intuited: tidak, itu tidak benar. Ketika jumlah nilai yang disimpan meningkat, Python akan secara otomatis meningkatkan ukuran hashtable, dan laju tabrakan tetap konstan. Dengan asumsi algoritma hash O (1) yang terdistribusi secara merata, maka pencarian hashtable diamortisasi O (1). Anda mungkin ingin menonton presentasi video "The Mighty Dictionary" python.mirocommunity.org/video/1591/…
Lie Ryan
13

Kita semua memiliki akses mudah ke sumbernya , di mana komentar sebelumnya set_lookkey()mengatakan:

/* set object implementation
 Written and maintained by Raymond D. Hettinger <[email protected]>
 Derived from Lib/sets.py and Objects/dictobject.c.
 The basic lookup function used by all operations.
 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
 The initial probe index is computed as hash mod the table size.
 Subsequent probe indices are computed as explained in Objects/dictobject.c.
 To improve cache locality, each probe inspects a series of consecutive
 nearby entries before moving on to probes elsewhere in memory.  This leaves
 us with a hybrid of linear probing and open addressing.  The linear probing
 reduces the cost of hash collisions because consecutive memory accesses
 tend to be much cheaper than scattered probes.  After LINEAR_PROBES steps,
 we then use open addressing with the upper bits from the hash value.  This
 helps break-up long chains of collisions.
 All arithmetic on hash should ignore overflow.
 Unlike the dictionary implementation, the lookkey function can return
 NULL if the rich comparison returns an error.
*/


...
#ifndef LINEAR_PROBES
#define LINEAR_PROBES 9
#endif

/* This must be >= 1 */
#define PERTURB_SHIFT 5

static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)  
{
...
Gimel
sumber
2
Jawaban ini akan mendapat manfaat dari C sintaks . Menyoroti sintaksis python dari komentar terlihat sangat buruk.
user202729
Mengenai komentar "Ini meninggalkan kita dengan hibrida penyelidikan linear dan pengalamatan terbuka", bukankah linear menyelidiki semacam resolusi tabrakan dalam pengalamatan terbuka, seperti yang dijelaskan dalam en.wikipedia.org/wiki/Open_addressing ? Oleh karena itu, penyelidikan linear adalah subtipe dari pengalamatan terbuka dan komentar tidak masuk akal.
Alan Evangelista
2

Untuk lebih menekankan perbedaan antara set'sdan dict's, di sini adalah kutipan dari bagian setobject.ckomentar, yang mengklarifikasi perbedaan utama dari himpunan terhadap dikt.

Gunakan case untuk set berbeda jauh dari kamus di mana mencari kunci lebih mungkin untuk hadir. Sebaliknya, set terutama tentang pengujian keanggotaan di mana keberadaan elemen tidak diketahui sebelumnya. Dengan demikian, implementasi himpunan perlu dioptimalkan untuk kasus yang ditemukan dan tidak ditemukan.

sumber di github

pengguna1767754
sumber