Algoritma baru ini untuk menyortir buku atau file mendekati kesempurnaan

Versi aslinya dari cerita ini muncul di Berapa banyak majalah.

Para ilmuwan komputer sering berurusan dengan masalah abstrak yang sulit dipahami, tetapi algoritma baru yang menarik bagi siapa saja yang memiliki buku dan setidaknya satu rak. Algoritma ini membahas sesuatu yang disebut masalah penyortiran perpustakaan (lebih formal, masalah “daftar pelabelan”). Tantangannya adalah merancang strategi untuk mengatur buku dalam semacam urutan yang diurutkan – secara alfabet, misalnya – bahwa meminimalkan berapa lama waktu yang dibutuhkan untuk meletakkan buku baru di rak.

Bayangkan, misalnya, bahwa Anda menjaga buku -buku Anda digumpal, meninggalkan ruang kosong di paling kanan rak. Kemudian, jika Anda menambahkan buku karya Isabel Allende ke koleksi Anda, Anda mungkin harus memindahkan setiap buku di rak untuk memberikan ruang untuk itu. Itu akan menjadi operasi yang memakan waktu. Dan jika Anda kemudian mendapatkan buku karya Douglas Adams, Anda harus melakukannya lagi. Pengaturan yang lebih baik akan meninggalkan ruang kosong yang didistribusikan ke seluruh rak – tetapi bagaimana, tepatnya, harus didistribusikan?

Masalah ini diperkenalkan di a Makalah 1981dan lebih dari sekadar menyediakan pustakawan dengan bimbingan organisasi. Itu karena masalahnya juga berlaku untuk pengaturan file pada hard drive dan dalam database, di mana item yang akan diatur dapat berjumlah miliaran. Sistem yang tidak efisien berarti waktu tunggu yang signifikan dan biaya komputasi utama. Para peneliti telah menemukan beberapa metode yang efisien untuk menyimpan barang, tetapi mereka sudah lama ingin menentukan cara terbaik.

Tahun lalu, di sebuah studi Itu disajikan di Foundations of Computer Science Conference di Chicago, tim yang terdiri dari tujuh peneliti menggambarkan cara untuk mengatur barang -barang yang mendekati cita -cita teoretis. Pendekatan baru ini menggabungkan sedikit pengetahuan tentang konten masa lalu rak buku dengan kekuatan keacakan yang mengejutkan.

“Ini masalah yang sangat penting,” kata Seth Pettieseorang ilmuwan komputer di University of Michigan, karena banyak struktur data yang kami andalkan saat ini menyimpan informasi secara berurutan. Dia menyebut karya baru itu “sangat terinspirasi [and] dengan mudah salah satu dari tiga makalah favorit saya tahun ini. ”

Batas penyempitan

Jadi bagaimana seseorang mengukur rak buku yang disortir dengan baik? Cara yang umum adalah melihat berapa lama waktu yang dibutuhkan untuk memasukkan item individual. Secara alami, itu tergantung pada berapa banyak item yang ada di tempat pertama, nilai yang biasanya ditunjukkan oleh N. Dalam contoh Isabel Allende, ketika semua buku harus bergerak untuk mengakomodasi yang baru, waktu yang dibutuhkan sebanding N. Semakin besar Nsemakin lama waktu yang dibutuhkan. Itu membuat ini menjadi “batas atas” untuk masalah: tidak akan pernah memakan waktu lebih lama dari waktu yang sebanding dengan N untuk menambahkan satu buku ke rak.

Para penulis makalah 1981 yang mengantarkan masalah ini ingin tahu apakah mungkin untuk merancang algoritma dengan waktu penyisipan rata -rata jauh lebih sedikit dari N. Dan memang, mereka membuktikan bahwa seseorang bisa melakukan yang lebih baik. Mereka menciptakan algoritma yang dijamin akan mencapai rata -rata waktu penyisipan sebanding dengan (log N)². Algoritma ini memiliki dua sifat: itu “deterministik,” yang berarti bahwa keputusannya tidak tergantung pada keacakan apa pun, dan itu juga “halus,” yang berarti bahwa buku -buku tersebut harus disebarkan secara merata di dalam sub -bagian rak di mana penyisipan (atau penghapusan) dibuat. Para penulis membiarkan pertanyaan apakah batas atas dapat ditingkatkan lebih jauh. Selama lebih dari empat dekade, tidak ada yang berhasil melakukannya.

Namun, tahun -tahun intervensi memang melihat perbaikan pada batas bawah. Sementara batas atas menentukan waktu maksimum yang diperlukan untuk memasukkan buku, batas bawah memberikan waktu penyisipan tercepat yang mungkin. Untuk menemukan solusi yang pasti untuk suatu masalah, para peneliti berusaha untuk mempersempit kesenjangan antara batas atas dan bawah, idealnya sampai mereka bertepatan. Ketika itu terjadi, algoritma dianggap optimal – secara terpisah dibatasi dari atas dan di bawah, tidak meninggalkan ruang untuk penyempurnaan lebih lanjut.

Pada tahun 2004, tim peneliti menemukan bahwa terbaik algoritma apa pun yang bisa dilakukan Untuk masalah penyortiran perpustakaan – dengan kata lain, batas bawah tertinggi – adalah log N. Hasil ini berkaitan dengan versi masalah yang paling umum, berlaku untuk algoritma apa pun dari jenis apa pun. Dua dari penulis yang sama telah mendapatkan hasil untuk versi masalah yang lebih spesifik pada tahun 1990, menunjukkan bahwa untuk algoritma yang halus, Batas bawah secara signifikan lebih tinggi: (log N)². Dan pada 2012, tim lain terbukti batas bawah yang sama(log N)²untuk algoritma deterministik apa pun yang tidak menggunakan keacakan sama sekali.

Hasil ini menunjukkan bahwa untuk algoritma yang halus atau deterministik, Anda tidak dapat mencapai waktu penyisipan rata -rata lebih baik daripada (log N)²yang sama dengan batas atas yang ditetapkan dalam makalah 1981. Dengan kata lain, untuk meningkatkan batasan atas itu, para peneliti perlu merancang jenis algoritma yang berbeda. “Jika Anda akan melakukan yang lebih baik, Anda harus acak dan tidak halus,” kata Michael Benderseorang ilmuwan komputer di Stony Brook University.

Tetapi menghilangkan kehalusan, yang mengharuskan barang -barang untuk disebarkan lebih atau kurang merata, tampak seperti kesalahan. (Ingat masalah yang muncul dari contoh awal kami-konfigurasi non-halus di mana semua buku digumpal bersama di sisi kiri rak.) Dan juga tidak jelas bagaimana meninggalkan segala sesuatu secara acak-pada dasarnya koin Lemparan – akan membantu masalah. “Secara intuitif, tidak jelas itu adalah arah yang masuk akal,” kata Bender.

Namun demikian, pada tahun 2022, Bender dan lima rekannya memutuskan untuk mencoba algoritma acak dan tidak halus, hanya untuk melihat apakah itu mungkin menawarkan keuntungan.

Sejarah Rahasia

Ironisnya, kemajuan datang dari pembatasan lain. Ada alasan privasi atau keamanan yang baik mengapa Anda mungkin ingin menggunakan algoritma yang buta terhadap sejarah rak buku. “Jika saya punya 50 nuansa abu -abu di rak buku saya dan melepasnya, ”kata William Kuszmaul Dari Universitas Carnegie Mellon, tidak ada yang bisa memberi tahu.

Dalam makalah 2022, bender, kuszmaul, dan empat rekan penulis menciptakan algoritma seperti itu-yang “independen sejarah,” non-halus, dan acak-yang akhirnya akhirnya mengurangi batas atas 1981menurunkan waktu penyisipan rata -rata ke (log N)^1.5.

Kuszmaul ingat terkejut bahwa alat yang biasanya digunakan untuk memastikan privasi dapat memberikan manfaat lain. “Seolah -olah Anda menggunakan kriptografi untuk membuat algoritma Anda lebih cepat,” katanya. “Yang sepertinya agak aneh.”

Helen Xu Dari Institut Teknologi Georgia, yang bukan bagian dari tim peneliti ini, juga terkesan. Dia mengatakan bahwa gagasan menggunakan independensi sejarah untuk alasan selain keamanan mungkin memiliki implikasi untuk banyak jenis masalah lainnya.

Menutup celah

Bender, Kuszmaul, dan lainnya membuat perbaikan yang lebih besar dengan makalah tahun lalu. Mereka kembali memecahkan rekor, menurunkan batas atas ke (log N) kali (log log N)³—Equivalent to (log N)^{1.000… 1}. Dengan kata lain, mereka sangat dekat dengan batas teoretis, batas bawah log tertinggi N.

Sekali lagi, pendekatan mereka tidak halus dan acak, tetapi kali ini algoritma mereka bergantung pada tingkat ketergantungan sejarah yang terbatas. Itu terlihat pada tren masa lalu untuk merencanakan acara mendatang, tetapi hanya sampai titik tertentu. Misalkan, misalnya, Anda telah mendapatkan banyak buku oleh penulis yang nama belakangnya dimulai dengan N – Nabokov, Neruda, Ng. Algoritma ekstrapolat dari itu dan mengasumsikan lebih banyak mungkin datang, jadi itu akan meninggalkan sedikit ruang ekstra di bagian N. Tetapi memesan terlalu banyak ruang dapat menyebabkan masalah jika sekelompok penulis a-name mulai menuangkan. “Cara kami membuatnya menjadi hal yang baik adalah dengan menjadi acak secara strategis tentang seberapa banyak sejarah untuk dilihat ketika kami membuat keputusan,” Bender dikatakan.

Hasilnya dibangun dan mengubah pekerjaan mereka sebelumnya. Ini “menggunakan keacakan dengan cara yang sama sekali berbeda dari kertas 2022,” kata Pettie.

Makalah ini secara kolektif mewakili “peningkatan yang signifikan” di sisi teori, kata Brian Wheatmanseorang ilmuwan komputer di University of Chicago. “Dan di sisi yang diterapkan, saya pikir mereka memiliki potensi peningkatan besar juga.”

Xu setuju. “Dalam beberapa tahun terakhir, ada minat dalam menggunakan struktur data berdasarkan label daftar untuk menyimpan dan memproses grafik dinamis,” katanya. Kemajuan ini hampir pasti akan membuat segalanya lebih cepat.

Sementara itu, ada lebih banyak teori untuk direnungkan. “Kami tahu bahwa kami hampir dapat melakukan log N“Kata Bender,”[but] Masih ada celah kecil ini ” – log log kecil N Istilah yang menghalangi solusi lengkap. “Kami tidak tahu apakah hal yang benar untuk dilakukan adalah menurunkan batas atas atau menaikkan batas bawah.”

Pettie, misalnya, tidak mengharapkan batas bawah berubah. “Biasanya dalam situasi ini, ketika Anda melihat celah sedekat ini, dan salah satu batas terlihat sangat alami dan yang lain terlihat tidak wajar, maka yang alami adalah jawaban yang tepat,” katanya. Jauh lebih mungkin bahwa setiap perbaikan di masa depan akan mempengaruhi batas atas, membawanya sampai ke log N. “Tapi dunia yang penuh kejutan aneh.”

Cerita asli dicetak ulang dengan izin dari Berapa banyak majalah, publikasi 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.