NewsInsight

[Analysis]

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

2008/03/24

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

　1度に60億匹とか70億匹という単位で、限られた地域で発生するために、アメリカでは迷惑な存在としてしか見られていないようだが、素数ゼミは生物学者たちにとっては、非常に好奇心をくすぐられる研究対象のようだ。

　吉村氏によれば、素数ゼミが素数年周期の、それも昆虫としてはかなり長期間のライフサイクルを持つに至ったのは氷河期の適応の名残だという。

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

ハッシュテーブルのリソース競合

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

　ハッシュテーブルとは、キーとなる文字列と値をセットで保存できるデータ構造のことで、PHP、JavaScript、Perl、Rubyといった軽量言語をはじめ、.NET環境やJavaなどでも標準的に用意されている。プログラマであれば日常的に使っているだろう。

　ハッシュテーブルは連想配列と呼ばれることもある。それはハッシュテーブルを、添え字に数字以外の文字列が利用できる配列と見なすことができるからだ。例えば英文ドキュメントに登場する語彙の出現頻度を調べるような場合、「apple、banana……」などの具体的な単語をキーとして、それらの単語の登場回数を値に保存することができる。appleという単語なら、count["apple"]に登場回数を保存して、随時インクリメントすればよい。

　文字列をキーにしてデータを記述できるのは便利だが、ハッシュテーブルの最大の特徴は、そうした記述上の利点にではなく、データ操作にかかる時間が一定ということにある。データの挿入や参照といった処理が、データ量に関係なく一定時間で終了する。

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

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

　うまくハッシュ関数を選ぶと、異なる文字列（キー）に対して異なるスロットを効率よく割り当てていけるが、それでも2つ以上の異なる文字列（キー）が同一のスロットに割り当てられてしまう“衝突”が起こるのは避けられない。可能な文字列の組み合わせの数に対してスロットの数がはるかに少ないからだ。

　スロットの衝突が起こったときの回避手法はいろいろあるが、あまり衝突頻度が高いようでは、そもそもハッシュテーブルを使う意味がなくなってしまう。そのためスロットが一定の割合、例えば7〜8割消費された時点で、多くの処理系は自動的にハッシュテーブルのサイズを大きくするようになっている。

　いずれにしても、キーが決まればスロット番号は一意に決まり、しかもその計算量は一定だ。だから、データ量が膨大でもデータの挿入や参照は一定時間に収まる。これはハッシュテーブルの重要な特徴であり長所だ。もし、ハッシュテーブルを使うべきところでリスト構造を使ってしまうと、データ量が増えるにしたがって処理速度が落ちてしまう。先ほどの英文ドキュメントの例でいえば数百ワードの文書を2つ3つ処理するだけなら、どんな方法でも同じようなものだが、百科事典のような膨大なテキストデータを相手にするとなると話が変わってくる。大きな百科事典に含まれる単語の種類は少なくとも数万個オーダーで、含まれる単語数は数千万オーダーとなるからだ。終わるべき計算が3日待っても終わらないということも起こりえる。

テーブルサイズを素数にして効率化

　ハッシュテーブルの効率は、ハッシュ関数と扱うデータの性質に依存しているが、より一般的に影響が大きいのはテーブルサイズだ。

　スロットの衝突頻度を低くするために、ハッシュテーブルのサイズは素数を使うのが望ましいことが経験的に確かめられている。64個のスロットよりも、67個のスロットを用意するほうがいい。

　例えば、Rubyでハッシュテーブルが実装されている部分（st.c）をのぞくと、次のように素数表がハードコーディングされているのが分かる（この部分のコードはカリフォルニア大学バークレー校のピーター・ムーア氏が書いたもの）。

static long primes[] = {
        8 + 3,
        16 + 3,
        32 + 5,
        64 + 3,
        128 + 3,
        256 + 27,
        512 + 9,
        1024 + 9,
           ：
           ：
        536870912 + 11,
        1073741824 + 85,
	0
};

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

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

コスト構造を意識する必要があるか

　素数ゼミとハッシュテーブルの関連性については完全に記者の思いつきなので妥当なのかどうかよく分からないが、ハッシュテーブルと素数の関係自体は古いテーマで、多くの読者がご存じだろう。

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

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

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

　逆に1度しか使わない使い捨てのデータ変換スクリプトや、社内で少人数しか使わない業務アプリケーションのようなソフトウェアでは、人間（プログラマ）の労働や学習コストが稀少なリソースだから、ソフトウェアの実行速度よりも生産性やメンテナンスの経済性を優先すべきだということになる。3秒かかる受発注処理を0.5秒に短縮する経済的合理性は見いだせないだろう。また、多くのソフトウェアで、処理速度のボトルネックはCPUの計算時間ではなく、ネットワーク処理やデータベースへのアクセス、あるいはI/O処理に存在するという事情もあり、CPUリソースを人的リソースより優先する理由は減ってきている。

　これは「アセンブラか高級言語か」というテーマで長年繰り返されてきた議論とも重なる。CPUの計算リソースが爆発的に増大するつれて、抽象度の高いプログラミング言語を使う場面が増えてきた。ただ、抽象度の高い言語を使うにしても、踏まえておくべき前提を飛ばさずに、適用限界を知った上で使うのが大切ということだ。

プログラマはどこまで常識として知っておくべきか

　Rubyで計算コストが見えづらいというのは、Rubyの問題というよりも抽象化が進んだ言語全般の問題だ。Rubyでもハッシュをリストと別物として提供するなど、データのアクセスパターンごとに別クラスに分離することで、計算コストを「見える人には見える」ようにデータ構造を抽象化しているから、問題はRubyにはない。問題は、抽象化の下で何が起こっているかを把握しているかどうか、あるいは意識すべきときはどういうときなのかをプログラマが理解しているかどうか、ということだ。データ構造の抽象化について、下のレイヤまで含めて理解しているプログラマと、そうでないプログラマでは最適化やデバッグの局面で大きな差が出るだろう。プログラミング言語の抽象度が上がっていく一方、常に「下のレイヤにも目を向けろ」「C言語で考えろ」「アセンブラをやっておけ」といった警鐘を鳴らす人々がいるのは、そういう理由があるからだ。

　コスト構造が見えづらいのでRubyを使うのは躊躇するといったSaaSベンダの開発者は、こうも言った。「世の中のプログラマと呼ばれている人のなかには、例えばハッシュテーブルの基本的な性質すら理解していない人もいる」。それは、プロ意識に欠ける凡百のプログラマなぞ、SaaSの波で洗い流してくれようと言わんばかりの発言だった。

　では、プログラマはハッシュテーブルの実装においてテーブルサイズとして素数が使われることがあるということや、その実用上の理由ぐらい常識として知っておくべきだろうか。ハッシュテーブルは1つの例でしかなく、いまやプログラマが踏まえておくべき議論はプログラミング言語や一般的なアルゴリズムの特性ばかりではなく、OSやCPUの内部構造、ストレージデバイスの構造と特性、各種ネットワークプロトコルの実績や特性いたるまで、非常に多岐にわたる。プログラミングの抽象度は上がり、CPUのレジスタのことは意識しなくなったかもしれないが、覚えるべきことは、むしろ急激に増えているのではないか。

　何をどこまで知っておくべきかは、どういうプログラムを作るかによって変わってくるので一概には言えないだろう。ただ、一般論として次のようなことは言えるのではないか。

　もし読者がプログラマであるとか、今後プログラマを目指すというのなら、こうした現実を前にして悲鳴を上げるべきではなく、大いに喜ぶべきだ。いくらでも深掘りすべき技術があり、いくらでも広げるべき知識の幅がある。いまやCPUリソースに比べて人間の知的労働というリソースは稀少だと書いたが、おそらくこれは正確ではない。本当に稀少なのは、幅広い知識、あるいは特定ジャンルで深い知識を備えた人的リソースだ。逆に、誰とでも容易に取り替え可能な単純なスキルセットしか持っていないプログラマは、安い労働力を提供する新興国のプログラマに置き換えられていくだろう。あるいは一握りの優秀なプログラマが作ったSaaS型アプリケーションに取って代わられるソフトウェアを前にして、仕事がなくなってしまうかもしれない。