紹介
- 新しいアルゴリズムが図書館の整列問題を解決する方法を提示している。
- この問題は、単に本を整列するだけでなく、ハードドライブやデータベースにおけるファイル配置にも適用される。
- 新しいアプローチは、本棚の過去の内容とランダム性を組み合わせることで、理論上の理想に近い結果を導く。
境界を狭める
- よく整列された本棚を測る一般的な方法は、個々の項目を挿入するのにかかる時間を見ることだ。
- 1981年の論文では、平均挿入時間が n よりはるかに小さいアルゴリズムを設計できるかという問いが提起された。
- 2004年の研究では、図書館整列問題の最適な下限が log n であることが発見された。
- 滑らかな、あるいは決定論的なアルゴリズムでは、平均挿入時間を (log n)² より良くすることはできないことが示された。
秘密の歴史
- 2022年、Bender とその同僚たちは、ランダムで非滑らかなアルゴリズムを試し、平均挿入時間を (log n)¹.⁵ まで縮めた。
- このアルゴリズムは過去の本棚の記録に依存せず、これはセキュリティ上の理由から有用である可能性がある。
ギャップを縮める
- Bender と Kuszmaul は上限を (log n) × (log log n)³ まで下げ、理論的下限に非常に近づいた。
- このアルゴリズムは、限られた程度の履歴依存性を用いて将来の出来事を計画する。
- この結果は以前の研究を土台としつつ、ランダム性をまったく異なる方法で利用している。
結論
- この研究は理論面で重要な改善を示しており、応用面でも大きな改善の可能性を持っている。
- 依然として log log n 項が完全な解決を妨げており、上限を下げるか下限を引き上げることが解決策になりうる。
1件のコメント
Hacker News のコメント
暗号化技術が性能向上に使えるという点が興味深い。性能とは単により多くの命令を実行することではなく、いかに仕事を減らすかを選ぶことだ。"履歴独立性"というセキュリティ特性は、過去を追跡する作業をしないことを意味する
記事で言及されている主要な論文を見つけるのが難しい。Quanta が記事の末尾に参考文献をすべて載せるようにすれば、読者の助けになるだろう
データベーステーブルで項目を任意に配置する問題を解決するために複雑なアルゴリズムが存在する。しかし、この問題の単純な解決策は分数値を使い、ときどきリストを再配置することだ
学生にこの問題を出したとき、'Library Sort' アルゴリズムをベースにしていたのを覚えている。元の論文のタイトルは 'Insertion Sort is O(n log n)' だ
現在使われているアルゴリズムより本当に速くなる理由があるのか疑問だ。B-tree ノードの配列では
memmove()を使うほうが速いかもしれない。大きな配列なら B ツリーを使うほうが簡単だ問題設定が固定長の事前割り当て配列を前提にしているのか気になる
英国図書館の本の管理方法には驚かされる。本が届くと電子カタログが残りを処理するので、本を並べ替える必要がない
記事上部のアニメーションをスクリーンセーバーにしたい
モバイルユーザー向けのクリーンなリンク
上界を
(log n) * (log log n)^3まで下げたということらしい。big-O 計算量において、多項式関連のクラスを扱っているときに対数がごくわずかな値を与えるのは興味深い