Versi aslinya dari cerita ini muncul di Berapa banyak majalah.
Suatu saat pada musim gugur 2021, Andrew Krapivin, seorang sarjana di Universitas Rutgers, menemukan sebuah makalah yang akan mengubah hidupnya. Pada saat itu, Krapivin tidak terlalu memikirkannya. Tetapi dua tahun kemudian, ketika dia akhirnya menyisihkan waktu untuk pergi melalui kertas (“hanya untuk bersenang -senang,” seperti yang dia katakan), upayanya akan mengarah pada pemikiran ulang alat yang banyak digunakan dalam ilmu komputer.
Judul kertas, “Pointer kecil”Rujuk ke entitas seperti panah yang dapat mengarahkan Anda ke sepotong informasi, atau elemen, dalam memori komputer. Krapivin segera datang dengan cara potensial untuk lebih meminimalkan pointer sehingga mereka mengkonsumsi lebih sedikit memori. Namun, untuk mencapai itu, ia membutuhkan cara yang lebih baik untuk mengatur data yang ditunjukkan oleh petunjuk.
Dia beralih ke pendekatan umum untuk menyimpan data yang dikenal sebagai tabel hash. Tetapi di tengah -tengah mengutak -atiknya, Krapivin menyadari bahwa ia telah menemukan jenis tabel hash baru, yang bekerja lebih cepat dari yang diharapkan – mengambil lebih sedikit waktu dan lebih sedikit langkah untuk menemukan elemen tertentu.
Martín Farach-Coltonrekan penulis makalah “Tiny Pointers” dan mantan profesor Krapivin di Rutgers, awalnya skeptis terhadap desain baru Krapivin. Tabel hash adalah salah satu struktur data yang paling dipelajari secara menyeluruh di semua ilmu komputer; Kemajuan terdengar terlalu bagus untuk menjadi kenyataan. Tapi hanya untuk memastikan, dia bertanya kepada kolaborator yang sering (dan rekan penulis “pointer kecil”), William Kuszmaul dari Universitas Carnegie Mellon, untuk memeriksa penemuan muridnya. Kuszmaul memiliki reaksi yang berbeda. “Kamu tidak hanya datang dengan meja hash yang keren,” kenangnya memberi tahu Krapivin. “Kamu benar-benar benar-benar memusnahkan dugaan berusia 40 tahun!”
Tanpa berangkat untuk melakukannya, Andrew Krapivin mengalahkan pemikiran umum di sekitar meja hash-salah satu alat yang dipelajari terbaik dalam ilmu komputer.
Bersama-sama, Krapivin (sekarang seorang mahasiswa pascasarjana di University of Cambridge), Farach-Colton (sekarang di Universitas New York), dan Kuszmaul ditunjukkan dalam a Kertas Januari 2025 Bahwa tabel hash baru ini memang dapat menemukan elemen lebih cepat dari yang dianggap mungkin. Karena itu, mereka telah membantah dugaan yang lama dianggap benar.
“Ini kertas yang penting,” kata Alex Conway Cornell Tech di New York City. “Tabel hash adalah salah satu struktur data tertua yang kami miliki. Dan mereka masih salah satu cara paling efisien untuk menyimpan data. ” Namun tetap ada pertanyaan terbuka tentang cara kerjanya, katanya. “Makalah ini menjawab beberapa dari mereka dengan cara yang mengejutkan.”
Tabel hash telah menjadi ada di mana -mana dalam komputasi, sebagian karena kesederhanaan dan kemudahan penggunaannya. Mereka dirancang untuk memungkinkan pengguna melakukan tepat tiga hal: “kueri” (cari) elemen, hapus elemen, atau masukkan satu ke dalam slot kosong. Tabel hash pertama berasal dari awal 1950 -an, dan para ilmuwan komputer telah mempelajari dan menggunakannya sejak itu. Antara lain, para peneliti ingin mencari tahu batas kecepatan untuk beberapa operasi ini. Seberapa cepat, misalnya, mungkin pencarian atau penyisipan baru?
Martín Farach-Colton membantu Krapivin membuktikan bahwa meja hash barunya bertentangan dengan dugaan lama.
Jawabannya umumnya tergantung pada jumlah waktu yang diperlukan untuk menemukan tempat kosong di tabel hash. Ini, pada gilirannya, biasanya tergantung pada seberapa penuh tabel hash. Kepenuhan dapat dijelaskan dalam hal persentase keseluruhan – tabel ini penuh 50 persen, bahwa 90 persen seseorang – tetapi peneliti sering berurusan dengan tabel yang lebih lengkap. Jadi sebagai gantinya, mereka dapat menggunakan bilangan bulat, dilambangkan dengan Xuntuk menentukan seberapa dekat tabel hash hingga 100 persen penuh. Jika X adalah 100, maka tabelnya 99 persen penuh. Jika X adalah 1.000, tabelnya 99,9 persen penuh. Ukuran kepenuhan ini menawarkan cara yang nyaman untuk mengevaluasi berapa lama waktu yang dibutuhkan untuk melakukan tindakan seperti pertanyaan atau penyisipan.
Para peneliti telah lama mengetahui bahwa untuk tabel hash umum tertentu, waktu yang diharapkan yang diperlukan untuk membuat penyisipan terburuk – memasukkan item ke dalam, katakanlah, tempat terbuka terakhir yang tersisa – sebanding dengan X. “Jika meja hash Anda 99 persen penuh,” kata Kuszmaul, “masuk akal bahwa Anda harus melihat sekitar 100 posisi berbeda untuk menemukan slot gratis.”
Di sebuah Makalah 1985ilmuwan komputer Andrew Yaosiapa yang akan memenangkan penghargaan AM Turing, menegaskan bahwa di antara tabel hash dengan serangkaian properti tertentu, cara terbaik untuk menemukan elemen individu atau tempat kosong adalah dengan hanya melalui bintik -bintik potensial secara acak – pendekatan yang dikenal sebagai probing yang seragam. Dia juga menyatakan bahwa, dalam skenario terburuk, di mana Anda mencari tempat terbuka terakhir yang tersisa, Anda tidak akan pernah bisa melakukan yang lebih baik dari X. Selama 40 tahun, sebagian besar ilmuwan komputer berasumsi bahwa dugaan Yao benar.
Krapivin tidak ditahan oleh kebijaksanaan konvensional karena alasan sederhana bahwa ia tidak menyadarinya. “Saya melakukan ini tanpa mengetahui tentang dugaan Yao,” katanya. Eksplorasi dengan pointer kecil menyebabkan jenis tabel hash baru – yang tidak bergantung pada penyelidikan yang seragam. Dan untuk tabel hash baru ini, waktu yang diperlukan untuk kueri dan insersi terburuk sebanding dengan (log X)2—Far lebih cepat dari X. Hasil ini secara langsung bertentangan dengan dugaan Yao. Farach-Colton dan Kuszmaul membantu Krapivin menunjukkan itu (log X)2 adalah batas optimal, tak terkalahkan untuk kelas populer dari tabel hash yang telah ditulis Yao.
“Hasil ini indah karena membahas dan memecahkan masalah klasik seperti itu,” kata Guy Blelloch dari Carnegie Mellon.
“Bukan hanya karena mereka membantah [Yao’s conjecture]mereka juga menemukan jawaban terbaik untuk pertanyaannya, ”kata Sepehr Assad dari University of Waterloo. “Kita bisa pergi 40 tahun lagi sebelum kita tahu jawaban yang benar.”
Krapivin di Jembatan King’s College di University of Cambridge. Tabel hash barunya dapat menemukan dan menyimpan data lebih cepat dari yang pernah dipikirkan oleh para peneliti.
Selain menyangkal dugaan Yao, makalah baru ini juga berisi apa yang banyak dianggap sebagai hasil yang lebih mencengangkan. Ini berkaitan dengan situasi yang terkait, meskipun sedikit berbeda, pada tahun 1985, Yao tidak hanya melihat waktu terburuk untuk pertanyaan, tetapi juga pada rata-rata waktu yang diambil di semua kueri yang mungkin. Dia membuktikan bahwa tabel hash dengan properti tertentu – termasuk yang diberi label “serakah,” yang berarti bahwa elemen baru harus ditempatkan di tempat pertama yang tersedia – tidak akan pernah mencapai waktu rata -rata lebih baik daripada log X.
Farach-Colton, Krapivin, dan Kuszmaul ingin melihat apakah batas yang sama juga diterapkan pada tabel hash non-greedy. Mereka menunjukkan bahwa itu tidak dengan memberikan contoh tandingan, tabel hash non-greedy dengan waktu kueri rata-rata yang jauh lebih baik daripada log X. Faktanya, itu tidak bergantung pada X sama sekali. “Anda mendapatkan nomor,” kata Farach-Colton, “sesuatu yang hanya konstan dan tidak bergantung pada seberapa penuh tabel hash.” Fakta bahwa Anda dapat mencapai waktu kueri rata -rata yang konstan, terlepas dari kepenuhan meja hash, sepenuhnya tidak terduga – bahkan bagi penulis sendiri.
Hasil tim mungkin tidak mengarah pada aplikasi langsung apa pun, tetapi tidak terlalu penting, kata Conway. “Penting untuk memahami struktur data semacam ini dengan lebih baik. Anda tidak tahu kapan hasil seperti ini akan membuka kunci sesuatu yang memungkinkan Anda melakukan lebih baik dalam latihan. “
Cerita asli dicetak ulang dengan izin dari Berapa banyak majalahpublikasi editorial independen dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman publik tentang sains dengan meliput perkembangan penelitian dan tren matematika dan ilmu fisik dan kehidupan.
