大学生が40年間信じられてきたデータサイエンスの定説を覆した (2/3)

『知らなかった』が生んだ革命

しかしその壁は、2025年1月に公開されたたった1本の論文で崩れ落ちることになります。

論文のタイトルは「並べ替えを行わないオープンアドレッシングの最適境界」。

クラピヴィン氏らがアーカイブ（arXiv）に投稿したこの論文は、あまりに鮮やかに壁を崩してみせたため、世界中の研究者を唖然とさせました。

ただ、この論文の凄さを楽しむには、ちょっとだけ準備運動が必要です。

難しい話ではなく、「ハッシュテーブルの速さ」には実は二つの顔があるのだと知っておくだけで十分です。

一つ目の顔は、一番運が悪かったときの速さ。

満室寸前のぎゅうぎゅうの棚に物を突っ込むとき、平均して何回くらい空き探しに失敗するか、という見方です。

もう一つは、全体をならしたときの速さ。

表にずらりと並んだ要素を一つずつ取り出していって、全部の平均を取るとどれくらいで済んでいるか、という見方です。

満員電車でたとえるなら、前者は「一番混む時間帯に駆け込んだときの所要時間」、後者は「一日を通した平均の乗り降り時間」。

この二つは別物で、片方だけ速くてもう片方は遅いということが普通に起きます。

さて、準備運動はこれだけです。

ではいよいよ、クラピヴィン氏らが何をやってのけたのかを見ていきましょう。

実はこの論文、新設計を一つではなく二つ同時に提示しています。

そしてこの二つが、それぞれ違う方向から、ヤオ予想とその周辺の難問を崩していくのです。

一つ目の設計「じょうご型ハッシング（funnel hashing）」。

これがまず信じがたい成果でした。

なにしろこの設計、40年来の暗黙のしきたりだった「貪欲ルール」――つまり「計算で割り当てられた候補を順番に試して、最初に見つけた空きにすぐ物を突っ込む」という素直なやり方――を律儀に守ったまま、運の悪いケースの速さを一気に改善してしまうのです。

どれくらい改善されるかというと、従来は棚の混み具合に正比例して試行回数が増えていたのに対し、じょうご型ではその「対数の二乗」程度にしか増えません。

対数というのは「大きな数をぐっと小さくしてしまう演算」だと思ってもらえれば十分で、たとえば従来なら100万回の試行が必要な最悪ケースが、じょうご型ではほんの数百回で片付いてしまう、というほどの差です。

ヤオが1985年に「貪欲ルールを守っている限り、こんなことは無理だろう」と予想したまさにそのことを、ルールを一文字も破らずにやってのけた――ヤオ予想が正面から覆された瞬間でした。

二つ目の設計「弾性ハッシング（elastic hashing）」。

こちらはさらに大胆です。

なんと40年来の貪欲ルール自体を、あえてぶち破ってしまうのです。

「最初に見つけた空きに即決で突っ込む」という素直な掟をいったん捨て、棚の先々まで一度ざっと下見をしてから、戻ってきてしかるべき場所に要素をそっと置く――そんな、一見すると遠回りに見える戦略を採ります。

ところが、この寄り道が思わぬ効果を生みました。

表の中にすでに入っている要素を取り出すときの平均の試行回数が、棚がどれだけ混んでいようと、ほぼ一定のまま動かなくなるのです。

長年「貪欲ルールを破ったらもっと速くできるかもしれないが、本当にできるのかは誰にも分からない」と言われ続けてきた、もう一つの大きな未解決問題への答えでした。

そしてこの論文の凄さは、ここで終わりません。

クラピヴィン氏らは「これまでより速くできる」と示しただけではなく、同じ論文の中で「これ以上はもう速くできない」という下限まで、数学的に証明してしまったのです。

じょうご型も弾性ハッシングも、「これより速い設計はもう作れない」ことが証明された最適解だった――つまり、40年越しの問題が、上限と下限の両方を同時に埋める形で完全に決着してしまったということです。

この成果は「穴が埋まった」というより、むしろ「扉が閉まった」事件だったと言えるかもしれません。

別々の二つの壁を、同じ一本の論文でほぼ同時にぶち破り、しかもその先に「もうこれ以上はない」という看板まで立ててみせた――これが、世界中の専門家をあれほど驚かせた本当の理由でした。

クラピヴィン氏がこの設計を最初に見せたのは、元指導教官のファラク＝コルトン氏でした。

ところが教授の最初の反応は、半信半疑だったと報じられています。

ハッシュテーブルはすでに何十年も研究され尽くされた分野で、学部生が根本的な改良を加える余地があるとは、とても思えなかったからです。

念のため共同研究者のクーズマウル氏に確認を依頼したところ、返ってきたのがあの「君は単にカッコいい仕組みを作っただけじゃない。40年来の予想を完全に吹き飛ばしたんだ」という一言でした。

取材の中で、クラピヴィン氏はこう語っています。

「僕はヤオ予想のことを知らずにこれをやりました」

知らなかったからこそ、「これは破れないはず」という心理的ブレーキが働かなかったのかもしれません。

もし彼が教科書通りに標準的な道筋をたどって学んでいたなら、一様ランダムに棚を試すという発想から離れること自体を、思いつかなかった可能性もあります。

ヤオが1985年に残した『1985年以来の壁』は、その存在を知らずに問題へ向き合った一人の若い研究者の自由な発想によって、ついに越えられました。

クラピヴィン氏は現在、イギリスのケンブリッジ大学で大学院生として研究を続けています。

知識は時に、次の発見を遠ざけていた――少し皮肉で、しかし希望に満ちたこの教訓は、私たちが最も身近に使うテクノロジーの奥底から、今あらためて投げかけられているのです。