Riset Mahasiswa S1 yang Membuktikan Peningkatan Kecepatan Pencarian dalam Tabel Hash

Pengantar

• Pada musim gugur 2021, mahasiswa S1 Rutgers University, Andrew Krapivin, menemukan sebuah makalah yang akan mengubah hidupnya.
• Makalah itu membahas "pointer kecil" yang menunjuk informasi di memori komputer.
• Krapivin merancang cara untuk membuat pointer lebih kecil sehingga mengurangi konsumsi memori.

Penemuan tabel hash baru

• Krapivin melakukan eksperimen menggunakan tabel hash, metode umum untuk menyimpan data.
• Selama eksperimen, Krapivin menemukan jenis baru tabel hash yang bekerja lebih cepat daripada yang sudah ada.
• Penemuan ini menghasilkan temuan yang membalikkan dugaan ilmu data yang telah bertahan selama 40 tahun.

Pentingnya tabel hash

• Tabel hash adalah salah satu struktur data tertua dalam ilmu komputer dan menawarkan efisiensi dalam penyimpanan data.
• Tabel hash dirancang agar dapat menjalankan tiga fungsi: mencari, menghapus, dan menyisipkan elemen.

Dugaan Yao dan bantahannya

• Pada 1985, ilmuwan komputer Andrew Yao mengajukan dugaan tentang cara menemukan elemen dalam kasus terburuk pada tabel hash dengan sifat tertentu.
• Tabel hash baru Krapivin membantah dugaan Yao dan membuktikan bahwa waktu yang dibutuhkan untuk kueri dan penyisipan pada kasus terburuk berbanding lurus dengan (log x)².

Temuan baru tentang waktu kueri rata-rata

• Krapivin dan timnya menunjukkan bahwa pada tabel hash non-greedy, waktu kueri rata-rata tidak bergantung pada x.
• Ini berarti waktu kueri rata-rata yang konstan dapat dicapai terlepas dari tingkat kepenuhan tabel hash.

Kesimpulan

• Riset ini memperdalam pemahaman tentang tabel hash dan berpotensi mengarah pada aplikasi praktis.
• Pemahaman tentang struktur data seperti ini dapat menjadi dasar bagi perbaikan praktis di masa depan.

[GN⁺]

Komentar Hacker News

• Krapivin membuat terobosan tanpa mengetahui dugaan Yao

  • Pengembang Balatro membuat game deck builder pemenang penghargaan tanpa mengetahui deck builder yang sudah ada
  • Cara terbaik untuk mendekati masalah mungkin adalah dengan tidak mengetahui atau mengabaikan upaya-upaya serupa sebelumnya
  • Dunia saat ini terlalu saling terhubung, sehingga mudah terjebak dalam kerangka pikir sebelumnya
  • Internet itu luar biasa, tetapi cenderung menyeragamkan dunia pemikiran

• Hasil yang keren, tetapi sepertinya ini seharusnya disebut dugaan ilmu komputer

• Saya penasaran apakah ada yang tahu repositori GitHub dengan implementasi ini

• Keren, tetapi gaya "pengkultusan tokoh" dalam artikel ini agak membuat tidak nyaman

  • Saya ragu apakah perlu melihat beberapa foto anak muda dengan berbagai pose di lingkungan kampus
  • Rasanya kita butuh versi La La Land untuk mendorong lebih banyak partisipasi dengan mengglorifikasi para penyintas sukses di dunia komputer

• Pada hash table baru ini, waktu yang dibutuhkan untuk query dan penyisipan dalam kasus terburuk berbanding lurus dengan (log x)²

  • Hasil tim ini mungkin tidak akan langsung mengarah ke penerapan praktis
  • Saya tidak paham mengapa ini tidak langsung mengarah ke penerapan praktis
  • Saya penasaran apakah ada situasi di mana analisis kasus penggunaan nyata dapat menyetel implementasi hash dengan lebih baik daripada pendekatan matematis murni

• Membaca artikel ini seperti membaca penjelasan masalah Monty-Hall

  • Kesimpulannya tampak bertentangan dengan akal sehat, tetapi bisa dibuktikan
  • Fakta bahwa waktu query rata-rata yang konstan bisa dicapai terlepas dari seberapa penuh hash table itu bahkan tidak diduga oleh para penulisnya sendiri

• Ini ujian yang bagus belakangan ini

  • Mari kita lihat apakah riset mendalam bisa menghasilkan ini tanpa sekadar menyalin hasilnya
  • gpt4, Gemini 2, Claude kurang beruntung
  • Ilmu komputer yang dipimpin manusia masih aman

• Saya penasaran apakah ada yang punya implementasi sederhana dari 'Tiny pointers'

  • Pikiran saya lebih dulu menuju kode/pseudocode daripada pembuktiannya

• Seperti yang selalu dikatakan penjahat di <i>Scooby Doo</i>:

  • <i>"Dan kalau bukan karena anak-anak usil itu, aku pasti sudah berhasil!"</i>

• Setelah membaca cepat makalahnya, tampaknya perbedaan utama yang mereka gunakan adalah bahwa algoritma penyisipan hash table mencari lebih jauh alih-alih secara rakus mengisi slot kosong pertama

  • Ini dipadukan dengan urutan pencarian yang terbukti dapat menemukan slot kosong secara efisien bahkan ketika tabel sangat penuh
  • Penyisipan menjadi lebih lambat saat hash table tidak terlalu penuh, tetapi ini bisa menghindari skenario terburuk saat gagal menemukan slot kosong terakhir yang tersisa

• Hasil teoretis yang menarik, tetapi dalam praktiknya rasanya 'trik' saat ini, yaitu mengalokasikan tabel yang lebih besar daripada yang diperlukan, akan menjadi solusi yang lebih baik

  • Misalnya, hashbrown milik Rust membiarkan 1/8 tabel (12,5%) tetap kosong, menggunakan sedikit lebih banyak memori tetapi membuat penyisipan/pencarian sangat cepat