ハッシュは"読み"間違えると遅いな
最適化に関してネットで調べてたら「ハッシュは本当に速いのか*1」という記事を見つけたから、自分の作ってるライブラリでも実験してみた。
実験は100000件のユニークなキーを持つデータを全て追加して、全て削除するというもの。擬似コードで書くと
for (int i=0; i
こんな感じ。containerの型をハッシュテーブルと二分木のそれぞれについて調べた。あくまで俺の作ったものであり、一般論ではないのでむやみに信じない方がいいかも。とにかく、結果は下のようになった。Hashの後の括弧はハッシュテーブルの大きさ。1024に固定したものと、データ数と同じ大きさのものを用意してみた。
Bench-mark (count = 5000) Hash(1024) : 0.0100 Hash(5000) : 0.0100 BTree : 0.0200 Bench-mark (count = 10000) Hash(1024) : 0.0500 Hash(10000) : 0.0200 BTree : 0.0400 Bench-mark (count = 50000) Hash(1024) : 2.2000 Hash(50000) : 0.1100 BTree : 0.2300 Bench-mark (count = 100000) Hash(1024) : 8.2900 Hash(100000): 0.2200 BTree : 0.4900
データ数が1024のハッシュはかなり悲惨な結果になっている。100,000件に対する応答が8秒は酷すぎる（多分俺の実装がだめ）。でも、データ数と同じ大きさのハッシュにしてやると、とっても安定する。計算してもらえば分かるけど、ハッシュ値がデータの数と同じならば処理時間も完全に比例する。
逆に、二分木（BTree）は常に安定して速い。現実問題としては100,000件のデータに対しても問題無いぐらいの速さだ（ものによるけど）。
さらに使用するメモリ量も見てみることにした。ライブラリ内のメモリ確保は全て専用の関数を通していて、デバッグモードでメモリの使用状況をダンプできるようにしてあったから、簡単に実験できた（こんなの計算してもいいんだけどね）。以下の結果は100,000件のデータ追加したときのコンテナのメモリ使用量。
Hash(1,024) : 1,604,116(byte) Hash(100,000) : 2,000,020(byte) BTree : 2,000,048(byte)
なんか微妙な結果だな。しかし、ひとつ言えるのはデータ総量が予測出来るのであれば、同じメモリでハッシュのほうが高速ということ。さらにメモリの節約などといってハッシュの大きさを小さくしても、メモリの節約結果の割りに、極端に遅くなる。
結論：
データの総量が予測出来るときはそのデータ量以上の大きさのハッシュ、予測出来ないときは二分木をつかうべし。
長々と、この当たり前の事導いただけか…。
