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

ということで、

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

ということですね。

基本情報の教科書を見ると、一番最初に出てくるのが、この２進数ですね。

２進数はコンピュータを設計する人にとっては、まさに必須なものなのですが、プログラマの中には無用という人も少なからずいるようです。

確かに、プログラム上で２進数を直接扱う機会は多くありません。
しかしながら、浮動小数型における循環小数など、２進数特有の特徴もあったりするので、知らないと分かりにくい罠にはまることもあります。

計算は面倒くさいものですが、まあこういうものなのだと割り切って、コンピュータの気持ちを少し理解してあげようではありませんか。

２進数とは？

我々の世界では、数字と言えば１０進数です。
１０ごとに位（くらい）が繰り上がるので、このように呼ばれています。

一方、コンピュータの世界では、２進数を使っています。
なぜか？
それは、電気や磁気といった科学的な現象を利用しているコンピュータの世界では、２つしか値が無いというシンプルな表現方式の方が、扱いやすいからです。

ちょうどタイムリーに、コン基礎の教え方の宝庫（1） 2進数の手ほどきという記事がITProにありましたので、引用したいと思います。

　いきなり「0と1だけで数を表すのが2進数です」なんて話をしたら、新人さんたちはとまどうでしょう。なぜ2進数を学ぶのか説明してから、様々な2進数の仕組を教えるべきです。私は、こんな風に説明しています。

1. コンピュータは、そもそも計算機として開発された。
2. 文字や画像など、本来数値でない情報を数値に置き換えて表すアイディアが生まれ、それによってコンピュータが、ただの計算機から万能の情報処理マシンになった。
3. 電気で数値を表すのに10進数を使うのは困難である。たとえば、1本の電線で10進数の1桁を伝えるために、電圧を0V～9Vと細かく制御するのは困難である。
4. そこで、1本の電線で電圧の有無だけを伝えることにした。これなら容易である。電圧無しを0、電圧有りを1とするのだ。1桁が0と1だけというのは、2進数である。
5. コンピュータの内部では、2進数で情報が取り扱われている。だから、コンピュータの仕組を理解するには、2進数を学ぶ必要があるのだ。現在のパソコンは、32本の電線を使って32桁の2進数を取り扱っている。

さすがは矢沢さん、とても分かりやすいと言いたいところですが、一つだけ間違いがありました。

そこで、1本の電線で電圧の有無だけを伝えることにした。これなら容易である。電圧無しを0、電圧有りを1とするのだ。1桁が0と1だけというのは、2進数である。

という部分ですね。
電圧無しを0としてしまうと、0だから電圧が無いのか、データが無いから電圧が無いのか、どこかに故障があるから電圧が無いのか、判断付かなくなってしまいます。

そこで、ケーブルに信号を流すときは、波形でもって1と0を表現するようにしています。
LANケーブルを例にすると、0と1は波形が上下逆であり、またプラスとマイナスに流れる電圧が同じになるように工夫されています。そうすることで、異常も検出しやすくしています。

矢沢さんの例に無い２進数を他に挙げると、スイッチのオン・オフ、磁界の向きなどもあります。
電圧のあるなしで言えば、コンデンサも２値を示すことができます。

位とは？

１０進数のときは、1の位、10の位、100の位．．．というように位を数えます。
２進数では、1の位、2の位、4の位、8の位．．．となりますが、なんだか覚えにくいですね。
この覚えにくさが、２進数の覚えにくさなのだと、私は考えています。

そこで、位とは何か考えてみましょう。
小学校の頃、位というものを習ったときは、1の位、10の位、100の位．．．と教えられましたが、ここで正体を明かしたいと思います。
その正体とは、

1の位　→　10⁰の位
10の位　→　10¹の位
100の位　→　10²の位
1000の位　→　10³の位

なのです。
つまり、10の何乗なのかで表現され、指数部は位が上がるごとに、0から1ずつ増えているだけです。
このときの10を基数と言います。
基数が10の数を１０進数、2の数を２進数、8の数を８進数、16の数なら１６進数となります。

従って、２進数の場合だと、

1の位　→　2⁰の位
2の位　→　2¹の位
4の位　→　2²の位
8の位　→　2³の位
16の位　→　2⁴の位

ということになります。
位が増えるごとに、基数にあたる2を掛けていけばよいのです。

基数変換

２進数から１０進数に変換したい場合は、
位を表す数とその値を掛けたものを、全て足していけばいいです。
例えば、1010 なら

1×8 + 0×4 + 1×2 + 0×1 = 10

となります。
または、

1×2³ + 0×2² + 1×2¹ + 0×2⁰ = 10

と表現してもいいですね。