- 図書館整列問題は本棚の整理にとどまらず、ハードドライブやデータベースにおける順次保存のコストを左右する。新しい研究は、平均挿入時間を理論上の限界に非常に近いところまで下げた
- 1981年のアルゴリズムは、決定的かつ**滑らかな（smooth）**方法で平均挿入時間 ((log n)^2) を保証したが、40年以上にわたり、これより低い上界は示されなかった
- その後の下界研究により、一般的なアルゴリズムで可能な最良は (log n)、滑らかなアルゴリズムと決定的アルゴリズムの限界は ((log n)^2) であることが示され、ランダム化された・非滑らかなアプローチが必要になった
- 2022年、Bender、Kuszmaulらは**履歴独立（history independent）**なランダム化アルゴリズムで上界を ((log n)^{1.5}) まで下げ、最新研究では限定的な過去情報も活用して ((log n)(log log n)^3) を達成した
- 残る差は (log log n) の項であり、この進展はリストラベリングに基づく動的グラフの保存・処理などの応用の高速化につながる可能性がある
図書館整列問題が問うもの
- 図書館整列問題は、整列済みの順序を保ちながら新しい項目を挿入するときに必要な移動時間を最小化する問題である
- 本を一方に詰めて置くと、途中に新しい本を入れる際に多くの本を移動し直さなければならない
- Isabel Allendeの本を追加するとき、すべての本を移動しなければならない場合がある
- その後Douglas Adamsの本を追加すると、同じ作業が繰り返される可能性がある
- 空きスペースを本棚全体に適切に分散させれば挿入コストを減らせるが、どこにどれだけスペースを残すかが核心となる
- より形式的には、**リストラベリング（list labeling）**問題と呼ばれ、1981年の論文で導入された
- 適用範囲は本棚を越え、ハードドライブやデータベースにおけるファイル・項目の配置にまで広がる
- 項目数が数十億に達することもある
- 非効率な配置は長い待ち時間と大きな計算コストにつながる
上界と下界で見る性能
- 整列済み配置の性能は通常、新しい項目を1つ挿入するのにかかる時間で評価する
- 項目数が (n) のとき、すべての本を移動しなければならないなら、挿入時間は (n) に比例する
- これは新しい項目の追加にかかり得る時間の上界と見なせる
- 1981年の論文は、平均挿入時間を (n) より大幅に減らせるかを問い、((log n)^2) を保証するアルゴリズムを示した
- ランダム性に依存しない決定的アルゴリズムである
- 挿入や削除が起こる区間内で項目が均等に広がっていなければならない、**滑らかな（smooth）**性質を持つ
- 研究者たちは上界と下界の差を縮め、2つの値が一致したときにアルゴリズムが最適だと判断する
既存の下界結果が生んだ制約
- 2004年の研究は、図書館整列問題の最も一般的なバージョンでは、どのアルゴリズムも (log n) より良くはできないという究極的な下界を示した
- 1990年には、滑らかなアルゴリズムの下界が ((log n)^2) であることが確認された
- 2012年には、ランダム性を使わない決定的アルゴリズムも同じ下界 ((log n)^2) を持つという結果が出た
- これらの結果は、滑らかなアルゴリズムや決定的アルゴリズムだけでは、1981年の ((log n)^2) という上界を改善するのは難しいことを意味する
- Michael Benderは、より良い結果にはランダム化されたかつ非滑らかなアルゴリズムが必要だと判断した
- 非滑らかな方法は項目を均等に間隔を空けて配置しないため、直感的には危険に見えた
- ランダムな選択がなぜ役立つのかも明らかではなかった
2022年：履歴独立で上界を下げる
- Bender、William Kuszmaulら6人は、2022年に履歴独立・非滑らか・ランダム化アルゴリズムを作った
- 履歴独立アルゴリズムは、本棚の過去の状態を明らかにしない
- Kuszmaulは、本棚にあった本を取り出したとき、他人がその事実を知ることはできないという例を挙げた
- こうした性質はプライバシーやセキュリティ上の理由で活用できる
- このアルゴリズムは1981年の上界を初めて下げ、平均挿入時間を ((log n)^{1.5}) に短縮した
- Kuszmaulは、通常はプライバシーのために使う道具がアルゴリズムをより速くし得る点を意外に受け止めた
- Georgia Institute of TechnologyのHelen Xuは、セキュリティ以外の理由で履歴独立を使うというアイデアが、他の問題にも影響を与える可能性があると評価した
最新研究：限定的な過去情報とランダム性の組み合わせ
- Bender、Kuszmaulらは最新論文で上界を再び下げ、((log n)(log log n)^3) を達成した
- この値は ((log n)^{1.000…1}) に相当し、究極的な下界である (log n) に非常に近い
- 新しいアプローチも非滑らかでランダム化されたものだが、今回は限定的な**履歴依存（history dependence）**を使う
- アルゴリズムは過去の傾向を一部見て、将来の挿入に備える
- Nabokov、Neruda、Ngのように姓がNで始まる著者の本が多く入ってきたなら、Nの区域に少し余裕を持たせる
- ただし、あまり多くのスペースを予約すると、Aで始まる著者の本が多く入ってきたときに問題になり得る
- Benderは、意思決定の際にどれだけ過去を見るかを戦略的にランダム化することで、このアプローチを有用にしたと説明する
- Seth Pettieは、今回の研究は2022年の論文とはまったく異なる方法でランダム性を使っていると評価した
残る差と応用可能性
- 残る差は小さな (log log n) の項である
- Benderは、上界をさらに下げるべきなのか、下界を引き上げるべきなのか、まだ分からないと述べる
- Pettieは、差がここまで狭く、一方の境界が自然で、もう一方が不自然に見えるときは、通常は自然な方が正解になると見ている
- 今後の改善は、上界を (log n) まで下げる方向である可能性がより高いと評価した
- ただし「世界は奇妙な驚きに満ちている」と付け加えた
- University of ChicagoのBrian Wheatmanは、これらの論文は理論的に相当な改善であり、応用面でも大きな改善の可能性があると見ている
- Helen Xuは近年、リストラベリングに基づくデータ構造で動的グラフを保存・処理することに関心を持っており、今回の進展はほぼ確実にそれを高速化すると見ている
1件のコメント
Hacker News のコメント
「プライバシー保護に使われていた道具が、別の利点ももたらし得る」という点には自分も驚いた
よく考えると、性能の大半は文字どおり「1時間あたりにより多くの命令を実行する」問題ではなく、より少なく作業する方法を選ぶことに近い
ここでセキュリティ上の性質である履歴独立性は、「履歴を追跡する作業をする必要もなく、文字どおりそれができもしない」という意味でもあるので、暗号学を制約として使い、不要な作業を防ぐという興味深い性能アプローチのように感じる
自分の理解では、計算時間はいくらでも使ってよいモデル
たとえばリストがソート済みだと分かっていれば二分探索を使える。だが、もしかするとどれだけ情報を省くかを選ぶことも核心になり得るのかもしれない。ただ、こういう場合はあまり頻繁には見かけず、簡単な例もすぐには思い浮かばない
記事で説明されている中心的な論文、つまり元の問題とほぼ最適なアルゴリズムの論文 [1]、[2] を探そうとしたのは自分だけなのか気になる
どちらも記事の奥のほうにリンクされているようだが、Quanta が記事末尾にすべての参考文献を必ずまとめてくれれば、読者にはとても助かると思う
[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
“This problem was introduced in a 1981 paper” の “1981 paper” が https://link.springer.com/chapter/10.1007/3-540-10843-2_34 にリンクされており、次の段落の “Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers” の “a study” が https://arxiv.org/abs/2405.00807 にリンクされている
どちらも導入部の3段落目、4段落目にあり、詳細・歴史・文脈に入る前だ。これを「記事の奥のほう」と言うなら、奥のほうの基準はかなり違わざるを得ない
先週まさにこの問題を見ていた。データベーステーブルの項目を任意の位置に置きたいが、できれば残りのリストには触りたくなかった
ユーザーが5番の項目の後ろに新しい要素を追加すると、その要素は6になるが、既存の5番の後ろにあった項目は更新しない、という具合。この問題を管理し、理論的限界を最小化する非常に洗練されたアルゴリズムは実際にある
ただしこの特定のバージョンでは、分数インデックスを使い、ときどきリストを再配置するコストを払うのが最も単純な解法に見えた
基本的には、ラベル空間が項目数に比べて大きければうまく動く。そうでない場合は、より洗練された方法が必要になる。たとえばラベルが4バイトしかなく、項目が10億個あるなら問題になる
記憶では、実際の解法は要素の間に間隔を残す方式だった。たとえば 0, 1, 2 の代わりに 0, 100, 200 のように置き、必要になったら再インデックスする。十分うまく動きそうだ
自分が思いついたのは、言われているような分数インデックスだったが、小数を扱うのは面倒なのでベクトルで表現し、それを辞書順にソートされる数字文字列として表せる
1 と 2 の間に挿入された要素のインデックスは 11 になる。11〜19 の間なら何でもよい。1 と 11 の間なら 101、11 と 2 の間なら 12、という具合。ただし、これらのインデックスは数値ではなく、辞書順で比較される文字列
欠点も明らかにありそうだ。たとえばこうしたインデックスをソートするには、メモリをはるかに多く使う。文字列は数値よりずっと大きいから。予期しない欠点がないにしては、賢すぎる感じもする
実際にはその限界はかなり限定的だが、単にコレクションに順序ラベルを付けるのではなく、このラベルを配列インデックスとして直接使って要素を保存しようとすると、その違いが本当に問題になる。そちらのほうが図書館ソート問題をより文字どおりモデル化した形だ
数年前、Library Sort アルゴリズムを基にした問題を学生たちに発表した記憶がある
元論文のタイトルはいまでもはっきり覚えている: “Insertion Sort is O(n log n)”
タイトルはかなりクリックベイトっぽい
このアルゴリズムが実際の現場で現在使われている方法より本当に速くなる理由があるのか気になる
自分がこの問題に主に出会ったのは B-tree ノード内の配列だが、そこでは単に
memmove()を使うより速いのか疑わしいし、本当に大きな配列なら B-tree を使うほうが簡単そうだだとすると、このアルゴリズムも漸近的にはより速いが、逆説的に実際に使われるアルゴリズムより遅い部類に入る。高速な行列乗算アルゴリズムが、良い実装の教科書的な O(n^3) アルゴリズム（GEMM）より遅いのがその例
そのページの最初の例には、有用性をよく説明する引用がある
「galactic algorithm の例として、2つの数を掛ける既知の最速の方法は 1729 次元フーリエ変換に基づいている。必要なのは O(n log n) ビット演算だけだが、ビッグオー記法の中に隠れた定数が大きいため、実際には使われていない。それでも、こうしたアルゴリズムがなぜ有用であり得るのかは示している。著者らは『さらなる改良により、数十億または数兆桁の数字だけで実用化されることを期待している』と述べている」
上限を (log n) × (log log n)^3 まで下げる — (log n)^(1.000...1) に相当するという話は事実多項式基準の系列として ビッグオー複雑度を見るときに面白い点の一つは、対数が無限小の値を与えること。「無限小は実際には存在しない」という人たちへの一撃になる
British Library が数百万冊の本と、毎週大量に入ってくる新刊をどう管理しているのかを知って驚いた
今年の初めに最初に入ってきた本は棚の 2025.0000001 の位置に置かれ、次の本はすぐ隣の 2025.0000002 に置かれた。残りは電子カタログが処理する
本を並べ替える必要はないが、書架を見て回って本を探す方法には合わない解決策だ
むしろ意図的に類似性を避け、ピッカーが似ているが違う商品を取らないようにしている
家でも、たまに使う物をどこに置いたかよく忘れる。x-acto ナイフの替刃をどのクローゼットのどの収納箱に入れたか、といったものだ。似た物同士でまとめようとするので、ある収納箱はあふれ、別の収納箱は半分空いていることもある
ときどき、持ち物をすべてスプレッドシートで追跡し、どの収納箱にあるか記録すれば、物をなくさず収納スペースも最大効率で使えるのではと想像する。だが新しい物を入れるときに更新を忘れるのは目に見えているし、人間よりロボットがやりそうな、非人間的に奇妙な方法に感じる
記事冒頭のアニメーションで スクリーンセーバーを作りたくなった
核心となる制約を把握しようとしている。問題定義は 固定長で事前に割り当てられた配列を仮定しているのか？
insert(X),delete(X),label(X)labelは、以前に挿入され、まだ削除されていない要素 X のラベルを取り出す。ラベルは 0 から n-1 までの数で、n は現在格納されている要素数