Geekly articles weekly

Implementasi kamus dengan Python

Halo semuanya, pada 30 April, kursus Algoritma untuk Pengembang dimulai di OTUS, dan publikasi materi hari ini didedikasikan untuk ini. Mari kita mulai.



Pada artikel ini, Anda akan belajar bagaimana kamus diimplementasikan dengan Python.
Kamus diindeks menggunakan kunci, dan mereka dapat dianggap sebagai array terkait. Mari kita tambahkan 3 pasangan kunci / nilai ke kamus:

>>> d = {'a': 1, 'b': 2} >>> d['c'] = 3 >>> d {'a': 1, 'b': 2, 'c': 3}

Nilai dapat diakses sebagai berikut:

 >>> d['a'] 1 >>> d['b'] 2 >>> d['c'] 3 >>> d['d'] Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 'd'

Kunci “d” tidak ada, sehingga kesalahan KeyError akan terjadi.

Tabel hash

Kamus dengan Python diimplementasikan menggunakan tabel hash. Mereka adalah array yang indeksnya dihitung menggunakan fungsi hash. Tujuan dari fungsi hash adalah untuk mendistribusikan kunci secara merata dalam array. Fungsi hash yang baik meminimalkan jumlah tabrakan, mis. kemungkinan bahwa kunci yang berbeda akan memiliki hash yang sama. Tidak ada fungsi hash seperti itu di Python. Fungsi hash yang paling penting (untuk nilai string dan integer) menghasilkan nilai yang serupa dalam kasus umum:

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

Kami akan menganggap bahwa sampai akhir artikel ini kami akan menggunakan string sebagai kunci. Fungsi hash dalam Python untuk string didefinisikan sebagai berikut:

 arguments: string object returns: hash function string_hash: if hash cached: return it set len to string's length initialize var p pointing to 1st char of string object set x to value pointed by p left shifted by 7 bits while len >= 0: set var x to (1000003 * x) xor value pointed by p increment pointer p set x to x xor length of string object cache x as the hash so we don't need to calculate it again return x as the hash

Jika Anda menjalankan hash('a') dengan Python, ia akan 12416037344 string_hash() dan mengembalikan 12416037344 . Di sini kita menggunakan mesin 64-bit secara default.

Jika array ukuran digunakan untuk menyimpan pasangan nilai / kunci, maka mask akan digunakan untuk menghitung indeks sel sel dalam array, yang dihitung sebagai -1 . Pendekatan ini membuat penghitungan indeks sel dengan cepat. Probabilitas menemukan sel kosong cukup tinggi karena mekanisme pengubahan ukuran, yang dijelaskan di bawah ini. Ini berarti bahwa perhitungan sederhana masuk akal dalam banyak kasus. Ukuran array adalah 8, indeks untuk 'a' akan menjadi: hash('a') & 7 = 0 . Indeks untuk 'b' adalah 2, indeks untuk 'c' adalah 3, indeks untuk 'z' adalah 3, sama seperti untuk 'b' , dan di sinilah kita mendapatkan tabrakan.



Seperti yang bisa kita lihat, fungsi hash di Python melakukan tugasnya dengan cara yang berkualitas ketika kunci berurutan, yang bagus, karena Anda sering harus bekerja dengan data tersebut. Namun, segera setelah kami menambahkan kunci 'z' , tabrakan terjadi karena tidak konsisten dengan yang sebelumnya.

Kita dapat menggunakan daftar tertaut untuk menyimpan pasangan, sementara memiliki hash yang sama, tetapi ini akan meningkatkan waktu pencarian, dan itu tidak akan sama dengan rata-rata O (1). Bagian berikut ini menjelaskan metode resolusi tabrakan yang digunakan untuk kamus dengan Python.

Buka pengalamatan

Open Addressing adalah teknik resolusi tabrakan yang menggunakan probing. Dalam kasus 'z' , indeks sel 3 sudah digunakan dalam array, jadi kita perlu mencari indeks lain yang belum digunakan. Operasi menambahkan pasangan kunci / nilai mengambil rata-rata O (1), serta operasi pencarian.

Untuk mencari sel bebas, digunakan urutan pencarian kuadratik. Diimplementasikan sebagai berikut:

 j = (5*j) + 1 + perturb; perturb >>= PERTURB_SHIFT; use j % 2**i as the next table index;

Rekursi pada (5 * j) +1 dengan cepat meningkatkan perbedaan besar dalam bit yang tidak mempengaruhi indeks asli. Variabel "perturb" dalam kasus ini mengambil bit lain dari kode hash.

Mari kita lihat dari keingintahuan apa yang terjadi jika kita memiliki urutan sampel dengan ukuran tabel 32 dan j = 3.

3 -> 11 -> 19 -> 29 -> 5 -> 6 -> 16 -> 31 -> 28 -> 13 -> 2 ...

Anda dapat mempelajari lebih lanjut tentang urutan penyelidikan ini dengan merujuk ke kode sumber dictobject.c . Penjelasan terperinci tentang mekanisme menyelidik dapat ditemukan di bagian atas file.



Mari kita lihat kode sumber Python dengan contoh ini.

Struktur kamus C

Struktur C berikut digunakan untuk menyimpan entri dalam kamus: pasangan kunci / nilai. Hash, kunci, dan nilai disimpan. PyObject adalah kelas dasar untuk objek dalam Python.

 typedef struct { Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value; } PyDictEntry;

Struktur berikut adalah kamus. ma_fill adalah jumlah total sel yang digunakan dan tidak aktif. Sel dianggap tidak aktif ketika pasangan kunci dihapus. ma_used adalah jumlah sel yang digunakan (aktif). ma_mask sama dengan ukuran array -1 dan digunakan untuk menghitung indeks sel. ma_table adalah array, dan ma_smalltable adalah array asli ukuran 8.

 typedef struct _dictobject PyDictObject; struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; Py_ssize_t ma_used; Py_ssize_t ma_mask; PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE]; };

Inisialisasi kosakata

Saat Anda baru saja membuat kamus, fungsi PyDict_New() . Saya menghapus beberapa baris dan mengonversi kode C ke kode semu untuk fokus pada konsep-konsep kunci.

PyDict_New() :

  • Mengembalikan objek kamus;
  • Mengalokasikan objek kamus baru;
  • Menghapus tabel kamus;
  • Setel jumlah sel kamus yang digunakan dan sel yang tidak digunakan ( ma_fill ) menjadi 0;
  • Setel jumlah sel aktif ( ma_used ) ke 0;
  • Menetapkan topeng kamus ( ma_value ) ke nilai yang sama dengan ukuran kamus - 1 = 7;
  • Mengatur fungsi pencarian kamus lookdict_string ;
  • Mengembalikan objek kamus yang dialokasikan.

Tambahkan item

Ketika pasangan kunci / nilai baru ditambahkan, PyDict_SetItem() dipanggil. Fungsi ini menerima pointer ke objek kamus dan pasangan kunci / nilai sebagai input. Ia memeriksa apakah kuncinya adalah string dan mengevaluasi hash atau menggunakan kembali cache jika ada. insertdict() dipanggil untuk menambahkan pasangan kunci / nilai baru dan ukuran kamus berubah jika jumlah sel yang digunakan dan yang tidak digunakan lebih dari 2/3 dari ukuran array.

Kenapa tepatnya 2/3? Ini diperlukan untuk memastikan bahwa urutan penyelidikan dapat menemukan sel bebas dengan cukup cepat. Nanti kita akan mempertimbangkan fungsi untuk mengubah ukuran.

 arguments: dictionary, key, value returns: 0 if OK or -1 function PyDict_SetItem: if key's hash cached: use hash else: calculate hash call insertdict with dictionary object, key, hash and value if key/value pair added successfully and capacity over 2/3: call dictresize to resize dictionary's table

inserdict() menggunakan fungsi pencarian lookdict_string() untuk menemukan sel gratis. Fungsi yang sama digunakan untuk mencari kunci.

lookdict_string() menghitung indeks sel menggunakan nilai hash dan mask. Jika dia tidak dapat menemukan kunci dengan nilai indeks sel = hash & mask (indeks slot = hash & mask), dia mulai memeriksa menggunakan siklus yang dijelaskan di atas sampai dia menemukan sel bebas. Pada upaya pertama untuk menyelidiki, jika kuncinya adalah null , itu mengembalikan sel yang tidak digunakan jika ditemukan selama pencarian pertama. Ini memastikan prioritas untuk menggunakan kembali sel yang sebelumnya dihapus.
Kami ingin menambahkan pasangan kunci / nilai berikut: {'a': 1, 'b': 2′, 'z': 26, 'y': 25, 'c': 5, 'x': 24} . Inilah yang akan terjadi:

Struktur kamus dialokasikan dengan ukuran tabel 8.

  • PyDict_SetItem: key = 'a', value = 1
    • hash = hash ('a') = 12416037344
    • insertdict
      • lookdict_string
        • indeks slot = hash & mask = 12416037344 & 7 = 0
        • slot 0 tidak digunakan, kembalikan sel ini
      • inisialisasi entri pada indeks 0 dengan kunci, nilai dan hash
      • ma_used = 1, ma_fill = 1
  • PyDict_SetItem: key = 'b', value = 2
    • hash = hash ('b') = 12544037731
    • insertdict
      • lookdict_string
        • indeks slot = hash & mask = 12544037731 & 7 = 3
        • slot 3 tidak digunakan, kembalikan sel ini
      • inisialisasi entri pada indeks 3 dengan kunci, nilai dan hash
      • ma_used = 2, ma_fill = 2
  • PyDict_SetItem: key = 'z', value = 26
    • hash = hash ('z') = 15616046971
    • insertdict
      • lookdict_string
        • indeks slot = hash & mask = 15616046971 & 7 = 3
        • slot 3 digunakan, coba sel lain: 5 gratis

        inisialisasi entri pada indeks 5 dengan kunci, nilai dan hash
        ma_used = 3, ma_fill = 3
  • PyDict_SetItem: key = 'y', value = 25
    • hash = hash ('y') = 15488046584
    • insertdict
      • lookdict_string
        • indeks slot = hash & mask = 15488046584 & 7 = 0
        • slot 0 digunakan, coba sel lain: 1 gratis
      • inisialisasi entri pada indeks 1 dengan kunci, nilai dan hash
      • ma_used = 4, ma_fill = 4

PyDict_SetItem: key = 'c', value = 3
  • hash = hash ('c') = 12672038114
  • insertdict
    • lookdict_string
      • indeks slot = hash & mask = 12672038114 & 7 = 2
      • slot 2 tidak digunakan, kembalikan sel ini
    • inisialisasi entri pada indeks 2 dengan kunci, nilai dan hash
    • ma_used = 5, ma_fill = 5

PyDict_SetItem: key = 'x', value = 24
  • hash = hash ('x') = 15360046201
  • insertdict
    • lookdict_string
      • indeks slot = hash & mask = 15360046201 & 7 = 1
      • slot 1 digunakan, coba sel lain: 7 gratis
    • inisialisasi entri pada indeks 7 dengan kunci, nilai dan hash
    • ma_used = 6, ma_fill = 6

Inilah yang kami dapatkan:



Sekarang 6 dari 8 sel digunakan, lebih dari 2/3 dari kapasitas array ditempati. dictresize() dipanggil untuk mengalokasikan array yang lebih besar. Fungsi ini juga menyalin catatan dari tabel lama ke yang baru.

dictresize () dipanggil dengan minused = 24 dalam kasus kami, di mana 4 * ma_used . 2 * ma_used digunakan ketika jumlah sel yang digunakan sangat besar (lebih dari 50.000). Mengapa sel 4 kali lebih banyak? Ini mengurangi jumlah langkah untuk menerapkan pengubahan ukuran dan meningkatkan sparseness.

Ukuran baru tabel harus lebih besar dari 24, itu dihitung dengan menggeser ukuran saat ini dengan 1 bit ke kiri sampai ukuran tabel menjadi lebih dari 24. Akibatnya, akan menjadi 32, misalnya, 8 -> 16 -> 32.

Inilah yang terjadi pada tabel kami selama mengubah ukuran: tabel baru ukuran 32 disorot. Entri tabel lama dimasukkan ke dalam tabel baru menggunakan nilai mask baru 31. Hasilnya adalah sebagai berikut:



Hapus item

PyDict_DelItem() dipanggil untuk menghapus catatan. Hash dihitung untuk kunci rekaman, lalu fungsi pencarian dipanggil untuk mengembalikan catatan. Sekarang selnya kosong.

Kami ingin menghapus kunci c dari kamus kami. Hasilnya, kami mendapatkan array berikut:



Perhatikan bahwa operasi menghapus elemen tidak mengubah ukuran array jika jumlah sel yang digunakan jauh lebih sedikit dari jumlah totalnya. Namun, ketika pasangan kunci / nilai ditambahkan, kebutuhan untuk mengubah ukuran tergantung pada jumlah sel yang digunakan dan tidak aktif, sehingga operasi penambahan juga dapat mengurangi array.

Publikasi ini telah berakhir, dan kami secara tradisional menunggu komentar Anda dan mengundang semua orang untuk pelajaran terbuka , yang akan diadakan pada tanggal 18 April.

Source: https://habr.com/ru/post/id448350/

More articles:


All Articles