BoostでC++0xのライブラリ「TR1」を先取りしよう (5)

はじめに

　C++の新しい規格「C++0x」では、言語とライブラリの両面から便利な機能が追加されます。「TR1」（Technical Report 1）はC++0xのライブラリ部で、標準C++に新たに追加されるライブラリの多くはBoostの中から選ばれたものです。2008年春にリリースが予定されているVisual Studio 2008にも追加パッケージとして供給されるとの情報を得ています。

　TR1に収録されたクラス/関数の中からいくつかをピックアップし、その概要と使い方を予習しておきましょう。これまでの一連の「TR1」解説ではBoostの実装を使ってきましたが、今回紹介する unorderedコンテナはBoostには含まれていません。そのため前述の追加パッケージ、Visual C++ 2008 Feature Pack Betaを使います。Feature Pack Betaは現時点では英語版Visual Studio 2008にのみ対応しています（VC++ 2008 Express 英語版でもNG）。いずれ日本語版にも対応してくれることでしょう。

"unordered"の意味

　標準C++ライブラリにはset、multiset、map、multimapの4つのコンテナが用意されています。これらは二分木（binary-tree）をその実装に用いたものです。大小関係に基づいて要素を二分木の枝にぶら下げたもので、挿入や検索に要する時間計算量はΟ(logN)すなわち要素数のlogに比例します。

　今回TR1で新たに追加された unordered_set、unordered_multiset、unordered_map、unordered_multimapは従来のset、multiset、map、multimapとそれぞれ機能的には同じです。異なるのはその実装、二分木ではなくハッシュ表（hash-table）が用いられています。最大の特徴はそのスピードにあります。

ハッシュ表が速いワケ

　ハッシュ表はくだけて言えば「一列に並んだバケツ」です。それぞれのバケツには通し番号が振られており、各バケツには複数のボール（要素）が格納できます。バケツはボールを要素とする可変長配列と考えていいでしょう。

　ここにバケツが一つあり、N個のボールが入っているとしましょう。ボールには番号が書いてあります。このとき適当な番号を指定して、その番号が書かれたボールをバケツの中から見つけだすことを考えます。

　バケツの中のボールは順不同ですから、目的のボールを見つけ出すには一つずつ取り出してはそれが目的のものであるかを調べなくてはなりません。好運に恵まれれば一個目のボールがお探しのボールですし、最悪のケースは最後まで調べたけれど見つからなかったとき。平均すればボール探しに必要な比較回数はN/2すなわち検索に要する時間はNに比例します。

　ではバケツを二つ用意し、偶数番のボールを0番バケツに/奇数番のボールを1番バケツに入れてると約束しておきます。すると適当な番号のボールを見つけるには、その番号が偶数なら0番バケツ/奇数なら1番バケツの中身だけを調べればいい。ボールの番号に大きな偏りがないなら各バケツ内のボールはほぼ同数のN/2ですから、検索に要する時間はバケツ一個の場合の半分です。

　この調子でバケツ数をM個にし、各ボールはそれに振られた番号をMで割った余りが示すバケツに入れましょう。そうすると検索時に調べなければならないボールの数すなわち検索に要する時間はN/Mに短縮されます。

　ということは、MをNと同じくらいにしておけばN/Mがおおよそ1になります。これはボールの総数に関係なくほとんど瞬時に検索が終了することを意味します。要素の検索対象となる母集団の要素数を1に近づけることで検索スピードを上げようという戦略です。

　ここで重要なるは各ボールをどのバケツに格納するかを決定する手段です。上記の例では「ボール番号をバケツ数で割った余り」としていますが、もしボール番号に大きな偏りがあるとバケツ内のボール数に偏りが生じて検索時間が伸びてしまいます。ボールがたくさん詰まったバケツとほとんどカラッポのバケツができてしまいますからね。

　要素（ボール）x から何らかの一意な値（バケツ番号）を導出する関数を「ハッシュ関数 h(x)」と名付けましょう。ハッシュ関数 h が満たさなければならない条件は:

x = y なら h(x) = h(y)

　です。そうでないとボール検索時に入っているはずのない"あさってのバケツ"内を探してしまうことになりますから。

　ただし、x ≠ y でも h(x) = h(y) となることがあります。ハッシュ関数 h がバケツ番号を決定するので、xとyは同じバケツに格納されます。

　ハッシュ関数が返す値（ハッシュ値）が同じ要素群をシノニム（synonym:同義語）と呼んでいます。