Algoritme baru untuk menyusun buku, performanya nyaris sempurna

Pengantar

• Algoritme baru ini menunjukkan cara menyelesaikan masalah penyusunan di perpustakaan.
• Masalah ini tidak hanya berlaku untuk menyusun buku, tetapi juga dapat diterapkan pada penataan berkas di hard drive dan basis data.
• Pendekatan baru ini menggabungkan isi rak buku di masa lalu dengan keacakan untuk menghasilkan hasil yang mendekati ideal secara teoretis.

Mempersempit batas

• Cara umum untuk mengukur rak buku yang tersusun dengan baik adalah dengan melihat waktu yang dibutuhkan untuk menyisipkan item satu per satu.
• Makalah tahun 1981 mengajukan pertanyaan apakah mungkin merancang algoritme dengan waktu penyisipan rata-rata yang jauh lebih kecil daripada n.
• Penelitian tahun 2004 menemukan bahwa batas bawah optimal untuk masalah penyusunan perpustakaan adalah log n.
• Penelitian itu menunjukkan bahwa dengan algoritme yang mulus atau deterministik, waktu penyisipan rata-rata yang lebih baik daripada (log n)² tidak dapat dicapai.

Sejarah rahasia

• Pada 2022, Bender dan rekan-rekannya mencoba algoritme acak dan tidak mulus, lalu menurunkan waktu penyisipan rata-rata menjadi (log n)¹.⁵.
• Algoritme ini tidak bergantung pada catatan rak buku di masa lalu, yang dapat berguna karena alasan keamanan.

Menutup kesenjangan

• Bender dan Kuszmaul menurunkan batas atas menjadi (log n) × (log log n)³, sehingga sangat mendekati batas bawah teoretis.
• Algoritme ini menggunakan ketergantungan terbatas pada riwayat untuk merencanakan kejadian di masa depan.
• Hasil ini dibangun di atas penelitian sebelumnya dan menggunakan keacakan dengan cara yang sepenuhnya berbeda.

Kesimpulan

• Penelitian ini menunjukkan perbaikan penting dari sisi teoretis, sekaligus memiliki potensi besar untuk perbaikan dari sisi penerapan.
• Istilah log log n masih menghalangi solusi yang benar-benar tuntas, dan solusinya bisa berupa menurunkan batas atas atau menaikkan batas bawah.

[GN⁺]

Komentar Hacker News

• Menarik bahwa teknik kriptografi dapat digunakan untuk meningkatkan performa. Performa bukan sekadar mengeksekusi lebih banyak instruksi, melainkan memilih bagaimana melakukan lebih sedikit pekerjaan. Sifat keamanan "history independence" berarti tidak melakukan pekerjaan untuk melacak masa lalu

• Sulit menemukan makalah utama yang disebutkan dalam artikel. Akan membantu pembaca jika Quanta mencantumkan semua referensi di akhir artikel

  • [1] Nearly Optimal List Labeling: tautan
  • [2] A sparse table implementation of priority queues: tautan

• Ada algoritme kompleks untuk menyelesaikan masalah menempatkan item secara arbitrer dalam tabel basis data. Namun, solusi sederhana untuk masalah ini adalah menggunakan nilai pecahan dan sesekali menata ulang daftar

• Saya ingat pernah memberikan masalah kepada mahasiswa berdasarkan algoritme 'Library Sort'. Judul makalah aslinya adalah 'Insertion Sort is O(n log n)'

• Saya ragu apakah ini benar-benar punya alasan untuk lebih cepat daripada algoritme yang digunakan saat ini. Dalam array node B-tree, menggunakan memmove() mungkin lebih cepat. Untuk array besar, lebih mudah menggunakan B-tree

• Saya penasaran apakah pernyataan masalah ini mengasumsikan array tetap dengan panjang yang sudah dialokasikan sebelumnya

• Saya terkejut dengan cara British Library mengelola buku. Saat buku tiba, katalog elektronik menangani sisanya sehingga tidak perlu menata ulang buku

• Saya ingin menjadikan animasi di bagian atas artikel sebagai screensaver

• Tautan yang rapi untuk pengguna seluler

  • Game: tautan
  • Kode: tautan
  • Sumber daya geometri subpiksel: tautan

• Benar bahwa batas atasnya diturunkan menjadi (log n) dikali (log log n)^3. Menarik bahwa log memberikan nilai yang sangat kecil dalam kompleksitas big-O saat menggunakan kelas acuan polinomial