Entry

プログラミング・メモ - ハッシュは速いとは限らないという話

2008年09月01日

こちらの話から。

関数benchはintを要素の型とするコンテナに[0,N)の範囲のN個の要素を挿入/削除し、それに要する時間および要素1個あたりの時間を出力します。

(snip)

ハッシュ・コンテナは二分木に比べて複雑です。ハッシュ値を求め、その値に対応するスロットに要素を挿入します。必要に応じて全要素の再配置を行わなければならないこともあるでしょう。それに比べたら要素の比較を繰り返す二分木の方が速いという結果もうなずけます。

ハッシュは本当に速いのか?

衝突時のアルゴリズムとテーブルサイズがどんなもんなのか分からないと,性能評価ができないんですけれど,二分木よりも遅くなる場合ってのはあるみたいです。まぁ,そうなのかもな……。極端な話,衝突時のアルゴリズムにチェイン法を使って,テーブルサイズを1にしたら,データ構造上リニアリンクと変わりません。ハッシュキーを計算する時間分だけ,むしろリニアサーチより遅くなる可能性すらあります。

一方,上の実験では,二分木とハッシュの比較に int 型のデータを入れているわけですけれど,実際問題として,int 型のデータを格納するハッシュってのが,どういう場面で使われるのか,あまり想像できません。int 型ってことは,もう値になっているわけで,ハッシュ関数も普通にテーブルサイズで modular を取るだけ,といった,シンプルなもんで済むんだと思います。テーブルサイズも2の冪乗にすると最速になるはず(剰余をビット演算で求められるから)。まぁ,この場合,添字 n のテーブル要素に m{m | N * i + n (N はテーブルサイズ; i は任意の整数)} なる値が入るわけで,奇妙っちゃ奇妙なんですが。この点,一般的なハッシュコンテナはそういう使い方に最適化しているわけではなくて,prime がどうとかとか,上位何ビットの XOR を取ってとかいった処理をしているはず。整数を収めればいいだけのことに,余計なことをしているんだと思います。二分木は単純に来た値を比較しているだけなので,そりゃ速いわな……と。整数入れるなら,普通は二分木なんだろうね……と。

ハッシュで効果的なのは,やはり任意の長さを持った文字列を格納する場合なんだと思います。どんな長さの文字列が来ても,一定の長さの値(ハッシュ空間)に圧縮することができるので,格納時にやってくる文字列そのものに注目する必要がありません。

ということで,ハッシュに限らず,どんなデータに対しても万能なデータ構造ってのはないわけで,賢く使い分けたいところです。また,こゆのは公式的に覚えるもんでもないし(ハッシュ=速いのように),それぞれのコンテナにも特性があったりします。例えば,MFC のハッシュコンテナ(CMap)では,予想される最大のデータセットよりも20%程度大きくテーブルサイズを取っておくと,衝突を最小にできるんだとか(参照:CMap::InitHashTable (MFC))。

データ構造とアルゴリズムの特性や,使用するパッケージの特性を十分踏まえなきゃね,という話でした。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN