素数ゼミとハッシュテーブル

@ITに良記事が掲載されていました。
素数ゼミとハッシュテーブル

先日、テレビで見たのですが、今年は17年ゼミの大発生が予想されているそうです。
なんでもでかいアメリカらしく、大発生したら木を埋め尽くし、死骸で地面が真っ黒になる地獄絵図が見られるわけです。

　「素数ゼミ」と呼ばれる一風変わったセミをご存じだろうか。記者は2005年に出版された『素数ゼミの謎』（吉村仁、文芸春秋）で知ったのだが、北米には13年または17年周期で大量発生するセミがいるという。素数ゼミたちは、きっちり決まった年数を地中で過ごしてから、成虫となって地表に出てくる。6種ほど知られている素数ゼミたちは、それぞれ決まった年に一斉に地表に出てきて、わずか数週間という短い夏を生殖活動に捧げて、一斉に死んでしまう。次に彼らの子どもたちが地表に出てくるのは13年とか17年後だ。この2008年の夏にも、アメリカの中南部で大量発生が予想されている。

17年ゼミと言わず、素数ゼミと言っているのがポイント。
そういえば、日本のアブラゼミも7年でしたね。

　氷河期には気温低下で成長速度が鈍り、成虫になるまでの期間が長期化する。10、11、12、13年……という周期で成長するセミが登場する。ライフサイクルが長期化すると、地表に出たときに交尾する相手を見つけにくくなるため、同種間で周期の同期が起こる。こうした周期ゼミのうち素数年の周期を持つセミたちは、ほかの素数でない年周期のセミたちに出会う確率が小さい。このため、食料などのリソース競合で有利な素数年周期のセミたちがだけが、ほかの12年や15年周期のセミが絶滅した中で生き残った、というのが現在の仮説だ。11年や19年も素数だが、11年は短すぎ、19年は長すぎるというので13年と17年の種だけが存在する。

なるほど、確かに素数だと、他のセミの周期に合わない可能性が高いです。
素数同士でかち合う年は単純に掛けて、13年ゼミと17年ゼミの周期なら221年ということになります。
狙ったわけでもなく、自然の摂理でうまいことできており、大変美しい仕組みです。

　ハッシュテーブルの実装でも素数が活用されていて、素数ゼミときわめて似た発想でリソース競合の問題を解決している。

と、ここでセミの話から、ハッシュテーブルの実装に移ります。

　実装にもよるが、ハッシュテーブルは初期化時に一定サイズのテーブルを用意する。テーブルには各キーと値の組み合わせを対応させる“スロット”と呼ばれる入れ物がある。入れ物には通し番号が振ってあり、ここに順不同にキーを対応させていくことになる。テーブルサイズが64だとすると、0から63までのスロットがあるということになる。

　キーとなる文字列が与えられると、ハッシュテーブルを処理するライブラリは何らかのハッシュ関数でハッシュ値を計算する。この値をテーブルサイズで割った余りの数が、そのキーが対応付けられるスロット番号となる。

この割ったときの余りというのが、ポイントです。

　ハッシュ値を割り算して、その余りをスロット番号として扱うハッシュテーブルでは、テーブルサイズがキリのいい数だと都合が悪い。異なるハッシュ値に対して同一スロットが割り当てられる可能性が高くなるからだ（このことは直感的には理解できるが、それほど自明でもない。……と思うが記者には説明できない。ただ、実験的に確かめられているのは事実だ。計算機科学は世間の印象に反して理論だけですべてが片付くほど決定論的ではないということだろう）。

　生死の周期を素数年単位とすることでリソースの競合を回避した素数ゼミたちと、テーブルサイズを素数とすることでスロットの衝突を避けたハッシュテーブル。一方は人為的に考え出されたもので、他方は進化のなかで出現した現象という違いはあるが、両者には共通した戦略が潜んでいる。そう思うのは記者だけだろうか。ハッシュテーブルではハッシュ値をテーブルサイズで割るわけだが、それはあたかもセミたちの世代交代に相当するかのようだ。

無駄な衝突を避けるという意味では、素数ゼミと同じ理屈ということです。

　ハッシュテーブルにまつわるこうした議論の蓄積を、記者は最近まで知らなかった。あるSaaSベンダの開発者と話していたときに、Rubyを使いたくない理由として「計算処理のコスト構造が見えづらい」ことを挙げたので、説明を求めたところ、その例として出てきたのがハッシュテーブルをはじめとするデータ構造の話だった。

　Rubyでいう配列はC言語などの配列と異なり、pushメソッドやpopメソッドで配列サイズが伸張するし、deleteメソッドで特定の要素だけ取り除くといったこともできる。Rubyの配列は、スタックやリストと呼ばれるデータ構造も兼ね備えた非常に汎用性の高いデータの入れ物だ。Rubyではデータ構造や処理の実現方法の違いを隠蔽し、プログラマにとって使い勝手のよいシンプルな方法で提供する。

　Rubyの生みの親であるまつもと氏に、こうしたアプローチを“大クラス主義”と呼ぶのだと教わった。まつもと氏の話に納得した記者はしばらく、にわか大クラス主義信者となっていたのだが、「コスト構造が見えづらい」という指摘で少し目が覚めた。当たり前の話だが、データ構造には一長一短があり、対象とするデータや処理内容によって向き不向きがあるからだ。SaaSのように少数者が設計、実装し、多い場合には数百万とか数千万人が利用するアプリケーションでは計算コストを最適化する意味は大きく、Rubyのように内部的にどういう処理が行われているかが見えづらい言語を使うのがためらわれる、ということだ。

私は業務アプリを作ることが多いので、コストはあまり気にしていません。
処理時間が0.1秒増えたとして、利用者の人生にはほとんど影響を与えないからです。
もちろん、速度は大事なのですが、速度はO記法の計算量を重視しています。（早い話がアルゴリズムを重要視しています）

一方、SaaS開発者ともなると、大量のアクセスが同時に発生することを想定するので、当然のことながらコストの感覚は重要になってきます。
にも関わらず、多くのエンジニアはこのような視点を持ち合わせていないことが多いように思います。

ということで、

　もし読者がプログラマであるとか、今後プログラマを目指すというのなら、こうした現実を前にして悲鳴を上げるべきではなく、大いに喜ぶべきだ。いくらでも深掘りすべき技術があり、いくらでも広げるべき知識の幅がある。

ということですね。