Algoritme Baru untuk Menyortir Buku Mencapai Hasil yang Hampir Sempurna

 (quantamagazine.org)
2 poin oleh GN⁺ 2025-01-26 | 1 komentar | Bagikan ke WhatsApp
  • Masalah penyortiran perpustakaan tidak hanya soal merapikan rak buku, tetapi juga menentukan biaya penyimpanan sekuensial pada hard drive dan basis data; riset baru menurunkan waktu penyisipan rata-rata hingga sangat dekat dengan batas teoretis
  • Algoritme tahun 1981 menjamin waktu penyisipan rata-rata ((log n)^2) dengan cara yang deterministik dan smooth (mulus), tetapi selama lebih dari 40 tahun tidak ada batas atas yang lebih rendah
  • Riset batas bawah berikutnya menunjukkan bahwa yang terbaik untuk algoritme umum adalah (log n), sementara batas untuk algoritme smooth dan algoritme deterministik adalah ((log n)^2), sehingga diperlukan pendekatan acak dan tidak smooth
  • Pada 2022, Bender, Kuszmaul, dan lainnya menurunkan batas atas menjadi ((log n)^{1.5}) dengan algoritme acak history independent (independen terhadap riwayat), dan riset terbaru mencapai ((log n)(log log n)^3) dengan memanfaatkan informasi masa lalu secara terbatas
  • Selisih yang tersisa adalah faktor (log log n), dan kemajuan ini dapat berujung pada peningkatan kecepatan dalam aplikasi seperti penyimpanan dan pemrosesan graf dinamis berbasis list labeling

Apa yang Ditanyakan Masalah Penyortiran Perpustakaan

  • Masalah penyortiran perpustakaan adalah masalah meminimalkan waktu pemindahan yang diperlukan saat memasukkan item baru sambil mempertahankan urutan tersortir
  • Jika buku ditumpuk rapat di satu sisi, saat memasukkan buku baru di tengah, banyak buku harus dipindahkan ulang
    • Saat menambahkan buku Isabel Allende, mungkin seluruh buku harus dipindahkan
    • Setelah itu, jika menambahkan buku Douglas Adams, pekerjaan yang sama bisa berulang
  • Menyebarkan ruang kosong secara tepat di seluruh rak dapat mengurangi biaya penyisipan, tetapi inti masalahnya adalah di mana dan seberapa banyak ruang harus disisakan
  • Secara lebih formal, ini disebut masalah list labeling, yang diperkenalkan dalam makalah tahun 1981
  • Cakupan penerapannya meluas melampaui rak buku hingga penempatan file dan item pada hard drive dan basis data
    • Jumlah item bisa mencapai miliaran
    • Penempatan yang tidak efisien dapat menyebabkan waktu tunggu panjang dan biaya komputasi besar

Performa Dilihat dari Batas Atas dan Batas Bawah

  • Performa penempatan tersortir biasanya dievaluasi berdasarkan waktu yang diperlukan untuk memasukkan satu item baru
  • Jika jumlah item adalah (n) dan semua buku harus dipindahkan, waktu penyisipan sebanding dengan (n)
    • Ini dapat dipandang sebagai batas atas waktu yang mungkin diperlukan untuk menambahkan item baru
  • Makalah tahun 1981 menanyakan apakah waktu penyisipan rata-rata dapat dibuat jauh lebih kecil daripada (n), dan menyajikan algoritme yang menjamin ((log n)^2)
    • Ini adalah algoritme deterministik yang tidak bergantung pada keacakan
    • Algoritme ini memiliki sifat smooth (mulus), yaitu item harus tersebar merata di dalam interval tempat penyisipan atau penghapusan terjadi
  • Para peneliti mempersempit jarak antara batas atas dan batas bawah, dan ketika kedua nilai itu cocok, algoritme dinilai optimal

Kendala yang Dibuat oleh Hasil Batas Bawah Sebelumnya

  • Riset tahun 2004 menunjukkan batas bawah final bahwa dalam versi paling umum dari masalah penyortiran perpustakaan, tidak ada algoritme yang bisa lebih baik daripada (log n)
  • Pada 1990, dikonfirmasi bahwa batas bawah untuk algoritme smooth adalah ((log n)^2)
  • Pada 2012, muncul hasil bahwa algoritme deterministik yang tidak menggunakan keacakan juga memiliki batas bawah yang sama, yaitu ((log n)^2)
  • Hasil-hasil ini berarti bahwa sulit memperbaiki batas atas ((log n)^2) dari tahun 1981 hanya dengan algoritme smooth atau algoritme deterministik
  • Michael Bender menilai bahwa untuk hasil yang lebih baik, diperlukan algoritme yang acak dan tidak smooth
    • Cara yang tidak smooth tampak berisiko secara intuitif karena tidak memberi jarak yang merata antar item
    • Mengapa pilihan acak bisa membantu juga belum jelas

2022: Menurunkan Batas Atas dengan Independensi Riwayat

  • Bender, William Kuszmaul, dan empat orang lainnya membuat algoritme history independent, tidak smooth, dan acak pada 2022
  • Algoritme history independent tidak mengungkap keadaan masa lalu rak buku
    • Kuszmaul memberi contoh bahwa ketika sebuah buku yang pernah ada di rak diambil, orang lain tidak bisa mengetahui fakta tersebut
    • Sifat seperti ini dapat dimanfaatkan untuk alasan privasi atau keamanan
  • Algoritme ini pertama kali menurunkan batas atas tahun 1981, memangkas waktu penyisipan rata-rata menjadi ((log n)^{1.5})
  • Kuszmaul menganggap mengejutkan bahwa alat yang biasanya dipakai untuk privasi bisa membuat algoritme menjadi lebih cepat
  • Helen Xu dari Georgia Institute of Technology menilai bahwa gagasan menggunakan independensi riwayat untuk alasan di luar keamanan dapat memengaruhi masalah lain juga

Riset Terbaru: Menggabungkan Informasi Masa Lalu Terbatas dan Keacakan

  • Dalam makalah terbaru, Bender, Kuszmaul, dan lainnya kembali menurunkan batas atas dan mencapai ((log n)(log log n)^3)
  • Nilai ini setara dengan ((log n)^{1.000…1}), sangat dekat dengan batas bawah final (log n)
  • Pendekatan baru ini juga tidak smooth dan acak, tetapi kali ini menggunakan history dependence (ketergantungan riwayat) secara terbatas
  • Algoritme melihat sebagian tren masa lalu dan bersiap untuk penyisipan di masa depan
    • Jika banyak buku dari penulis dengan nama belakang berawalan N seperti Nabokov, Neruda, dan Ng masuk, algoritme menyisakan sedikit lebih banyak ruang di area N
    • Namun, jika terlalu banyak ruang dicadangkan, itu bisa menjadi masalah saat banyak buku dari penulis berawalan A masuk
  • Bender menjelaskan bahwa ia membuat pendekatan ini berguna dengan mengacak secara strategis seberapa banyak masa lalu yang dilihat saat mengambil keputusan
  • Seth Pettie menilai riset ini menggunakan keacakan dengan cara yang sepenuhnya berbeda dari makalah tahun 2022

Selisih yang Tersisa dan Potensi Aplikasi

  • Selisih yang tersisa adalah faktor kecil (log log n)
  • Bender mengatakan belum diketahui apakah batas atas perlu diturunkan lebih jauh atau batas bawah perlu dinaikkan
  • Pettie berpandangan bahwa ketika selisih sudah sesempit ini dan satu batas terlihat alami sementara batas lainnya terlihat tidak alami, biasanya sisi yang alami menjadi jawaban
    • Ia menilai perbaikan mendatang lebih mungkin mengarah pada penurunan batas atas hingga (log n)
    • Namun, ia menambahkan bahwa “dunia penuh dengan kejutan aneh”
  • Brian Wheatman dari University of Chicago melihat makalah-makalah ini sebagai peningkatan besar secara teoretis, dan juga memiliki potensi peningkatan besar dari sisi aplikasi
  • Helen Xu tertarik pada penyimpanan dan pemrosesan graf dinamis dengan struktur data berbasis list labeling, dan menilai kemajuan ini hampir pasti akan membuatnya lebih cepat

Bacaan terkait

1 komentar

 
GN⁺ 2025-01-26
Komentar Hacker News

  • Aku juga terkejut bahwa “alat yang dipakai untuk perlindungan privasi bisa memberi manfaat lain juga”
    Kalau dipikir-pikir, sebagian besar kinerja pada dasarnya bukan soal harfiah “mengeksekusi lebih banyak perintah per jam”, melainkan lebih dekat ke memilih cara agar bekerja lebih sedikit
    Di sini, sifat keamanan berupa independensi riwayat juga berarti “tidak perlu, dan secara harfiah juga tidak bisa, melakukan pelacakan riwayat”, jadi terasa seperti pendekatan kinerja yang menarik: memakai kriptografi sebagai batasan untuk mencegah pekerjaan yang tidak perlu

    • Tafsiran itu tampaknya kurang tepat. Kalau kelambatan algoritme diukur dengan waktu komputasi, itu benar, tetapi metrik yang benar-benar diukur di sini adalah jumlah buku yang harus dipindahkan
      Sejauh yang kupahami, ini adalah model yang mengizinkan penggunaan waktu komputasi tanpa batas
    • Wawasan yang bagus. Aku selalu menganggap inti dari perancangan algoritme/struktur data yang baik adalah memanfaatkan semua informasi yang ada dalam dataset
      Misalnya, kalau kita tahu sebuah daftar sudah terurut, kita bisa memakai pencarian biner. Namun mungkin memilih berapa banyak informasi yang akan diabaikan juga bisa menjadi hal yang penting. Hanya saja, kasus seperti ini tampaknya lebih jarang, dan aku tidak langsung terpikir contoh sederhananya
    • Pada akhirnya ini terlihat seperti soal menemukan bagian mana dari konteks masalah yang bisa dan seharusnya disembunyikan secara selektif, agar algoritme bekerja bukan “lebih keras” melainkan “lebih cerdas”. Menarik juga
    • Sebenarnya algoritme yang lebih baik justru memakai ketergantungan riwayat. Jadi menurutku bagian artikel itu agak menyesatkan

  • Apa aku satu-satunya yang mencoba mencari makalah inti yang dijelaskan artikel, yaitu makalah tentang masalah aslinya dan algoritme yang hampir optimal [1], [2]?
    Keduanya tampaknya ditautkan jauh di dalam artikel, dan akan sangat membantu pembaca jika Quanta mewajibkan semua referensi dikumpulkan di akhir artikel
    [1] Nearly Optimal List Labeling:
    https://arxiv.org/abs/2405.00807
    [2] A sparse table implementation of priority queues:
    https://link.springer.com/chapter/10.1007/3-540-10843-2_34

    • Kedua makalah itu ditautkan dengan sangat jelas di artikel, dan bahkan dengan sekadar memindai tanpa membaca pun mudah ditemukan
      Di kalimat “This problem was introduced in a 1981 paper”, frasa “1981 paper” tertaut ke https://link.springer.com/chapter/10.1007/3-540-10843-2_34, dan di paragraf berikutnya, pada “Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers”, frasa “a study” tertaut ke https://arxiv.org/abs/2405.00807
      Keduanya ada di paragraf ketiga dan keempat bagian pengantar, sebelum artikel masuk ke rincian, sejarah, dan konteks. Kalau itu dianggap “jauh di dalam artikel”, berarti standar untuk menyebut sesuatu jauh di dalam memang cukup berbeda

  • Minggu lalu aku sedang melihat tepat masalah ini. Aku ingin menempatkan item-item dalam tabel database pada posisi arbitrer, tetapi sebisa mungkin tanpa menyentuh sisa daftar
    Jika pengguna menambahkan elemen baru setelah item nomor 5, elemen itu menjadi nomor 6, tetapi item yang sebelumnya ada setelah nomor 5 tidak perlu diperbarui. Memang ada algoritme yang sangat canggih untuk menangani masalah ini dan meminimalkan batas teoretisnya
    Namun untuk versi khusus ini, solusi paling sederhana tampaknya adalah memakai indeks pecahan, lalu sesekali membayar biaya untuk menata ulang daftar

    • Algoritme ini ada di bagian exponential labels di Wikipedia: https://en.m.wikipedia.org/wiki/List-labeling_problem
      Pada dasarnya ini bekerja baik jika ruang label besar dibanding jumlah item. Jika tidak, dibutuhkan metode yang lebih canggih. Misalnya, jika label hanya 4 byte dan item ada 1 miliar, itu menjadi masalah
    • Aku pernah mendapat masalah ini persis sebagai pertanyaan wawancara
      Kalau tidak salah, solusi nyatanya adalah menyisakan jarak di antara elemen. Misalnya, alih-alih 0, 1, 2, pakai 0, 100, 200 lalu lakukan pengindeksan ulang bila perlu. Sepertinya itu akan bekerja cukup baik
      Yang terpikir olehku, seperti yang disebutkan tadi, adalah fractional indexing, tetapi karena repot menangani angka pecahan, itu bisa direpresentasikan sebagai vektor, lalu dinyatakan sebagai string angka yang diurutkan secara leksikografis
      Elemen yang disisipkan di antara 1 dan 2 akan mendapat indeks 11. Bisa juga angka mana pun antara 11–19. Kalau di antara 1 dan 11, maka 101; kalau di antara 11 dan 2, maka 12; dan seterusnya. Namun indeks-indeks ini bukan angka, melainkan string yang dibandingkan secara leksikografis
      Tampaknya jelas ada kelemahannya juga. Misalnya, untuk mengurutkan indeks semacam ini, memori yang dipakai jauh lebih besar. String jauh lebih besar daripada angka. Rasanya terlalu pintar untuk tidak punya kelemahan tak terduga
    • Mirip nomor baris pada program BASIC zaman dulu
    • Secara teoretis, memakai pecahan sebagai label daftar membutuhkan memori tak terbatas untuk menyimpan pecahan itu
      Dalam praktiknya batas itu memang sangat terbatas, tetapi jika alih-alih sekadar memberi label urutan pada koleksi, kita mencoba langsung memakai label ini sebagai indeks array untuk menyimpan elemen, perbedaannya benar-benar menjadi masalah. Model itu lebih secara harfiah merepresentasikan persoalan penyortiran perpustakaan
    • Bukankah itu chaining pada hash table?

  • Aku ingat beberapa tahun lalu pernah mempresentasikan soal yang didasarkan pada algoritme Library Sort kepada para mahasiswa
    Judul makalah aslinya masih sangat membekas: “Insertion Sort is O(n log n)”

  • Saya penasaran apakah ada alasan algoritme ini benar-benar akan lebih cepat di lapangan dibanding cara yang saat ini dipakai
    Tempat saya paling sering menemui masalah ini adalah array node B-tree, dan di sana saya ragu ini akan lebih cepat daripada sekadar memakai memmove(), dan jika array-nya benar-benar besar, rasanya lebih mudah memakai B-tree
    Kalau begitu, algoritme ini juga termasuk golongan yang secara asimtotik memang lebih cepat tetapi secara ironis lebih lambat daripada algoritme yang benar-benar dipakai. Contohnya adalah algoritme perkalian matriks cepat yang lebih lambat daripada algoritme O(n^3) yang klasik dengan implementasi bagus (GEMM)

    • Algoritme seperti ini kadang disebut Galactic Algorithms: https://en.wikipedia.org/wiki/Galactic_algorithm
      Contoh pertama di halaman itu memuat kutipan yang menjelaskan kegunaannya dengan baik
      “Sebagai contoh galactic algorithm, cara tercepat yang diketahui untuk mengalikan dua bilangan didasarkan pada transformasi Fourier 1729-dimensi. Ini hanya memerlukan O(n log n) operasi bit, tetapi konstanta yang tersembunyi di dalam notasi Big O sangat besar sehingga dalam praktiknya tidak dipakai. Meski begitu, ini menunjukkan mengapa algoritme seperti ini bisa tetap berguna. Para penulis mengatakan mereka ‘berharap perbaikan lebih lanjut akan membuatnya praktis hanya untuk bilangan dengan miliaran atau triliunan digit’”

  • Pernyataan menurunkan batas atas menjadi (log n) × (log log n)^3 — setara dengan (log n)^(1.000...1) memang benar
    Salah satu hal keren saat melihat kompleksitas Big O dalam keluarga berbasis polinomial adalah bahwa log memberi nilai infinitesimal. Ini seperti serangan telak untuk orang-orang yang berkata “infinitesimal itu sebenarnya tidak ada”

    • Tunggu, apa? Adakah referensi yang bisa dipakai untuk mempelajari ini?

  • Saya terkejut mengetahui bagaimana British Library mengelola jutaan buku dan banyak sekali buku baru setiap minggu
    Buku pertama yang masuk tahun ini ditempatkan di rak pada posisi 2025.0000001, dan buku berikutnya tepat di sebelahnya pada 2025.0000002. Sisanya ditangani oleh katalog elektronik
    Tidak perlu menyusun ulang buku, tetapi ini bukan solusi yang cocok untuk cara mencari buku dengan menyusuri rak

    • Ini mengingatkan saya pada cara Amazon tidak menata barang seperti toko biasa, yang menempatkan barang serupa berdekatan. Model penyedot debu bisa berada di sebelah set piring dapur
      Mereka justru sengaja menghindari kemiripan agar picker tidak mengambil barang yang mirip tetapi salah
      Di rumah pun saya sering lupa menaruh barang yang kadang dipakai. Misalnya isi ulang bilah x-acto saya taruh di kompartemen lemari yang mana di dinding yang mana. Karena berusaha mengelompokkan barang serupa, satu kompartemen jadi penuh sesak sementara yang lain setengah kosong
      Kadang saya membayangkan jika semua barang saya dilacak di spreadsheet dan dicatat ada di kompartemen mana, saya tidak akan kehilangan barang dan ruang penyimpanan juga bisa dipakai seefisien mungkin. Tapi saya pasti akan lupa memperbaruinya saat menaruh barang baru, dan rasanya seperti cara yang tidak manusiawi dan aneh, lebih cocok dilakukan robot daripada manusia

  • Animasi di bagian paling atas artikel membuat saya ingin menjadikannya screen saver

  • Saya sedang mencoba memahami batasan utamanya. Apakah definisi masalahnya mengasumsikan array dengan panjang tetap yang dialokasikan sebelumnya?

    • Tidak, sama sekali tidak mengasumsikan array. Ini adalah struktur data yang mempertahankan himpunan dengan urutan total, dan operasinya ada tiga:
      insert(X), delete(X), label(X)
      label mengambil label dari elemen X yang sebelumnya sudah dimasukkan dan belum dihapus. Labelnya adalah angka dari 0 sampai n-1, dengan n adalah jumlah elemen yang sedang disimpan saat ini.