2011年02月15日

BDBで測定してみた

BDBで使えるデータ構造についてです。
BDB内の用語ではアクセスメソッドと呼ばれています。

recno


行単位なデータ構造
多分双方向リストと変わらない・・・?
行番号みたいな概念があるので
BDBでも次のデータとか前のデータみたいな指定の仕方ができます。
順番に処理したい時には適しているデータ構造ですね。

btree


いわゆる二分木ツリー。

btree


図にするとこんな感じ。
ツリーの偏りが控えめに構築できていれば
パフォーマンスは良いはず。
オーダーはLog Nとかになるんだったかな。

hash


一定の法則に基づいて、元の値に対するインデックスの値を求めます。
割り算が例に出されることが多いです。

例えばある数を、9で割った余りは0から8のどれかになります。
これをそのまま配列の添字にして格納すれば探索が一回でできるので
データの量と関係なく、一定の速度が期待できます。

これがkey-valueのペアだったりすると
keyに対応するvalueを一回の処理で探索できます。

hash


ところが、ここで疑問が出てくると思います。
元の値は違うけど、たまたま同じハッシュ値になったらどうするんだろう
そう、確かにそういう問題がはらんでいます。

なので
・ハッシュ値の範囲を広くする
・衝突した場合、そこにリストを作って管理する
という方法が採られています。
リストの例は、図の8番目の配列がそうですね。

衝突した場合は別ですが
エントリ数が多くても、検索にかかる処理は同じなので
大量のエントリを扱う場合はハッシュが適しているかと思います。
ただし、使われないメモリ領域も確保する必要があるので
無駄が生じます。
図で言うと2,5,8以外は使っていませんしね。

測定してみた


このように、データ構造ごとに特徴がありますが
実際、性能の差はどんなものだろうということで測定してみました。

内容としてはスクリプトを使って
100000回くらいDBへのPUTを実行し
一回一回のPUTにかかった時間を測定してみました。

結果としては
  • ハッシュは極端に遅いケースがあるが安定している
  • エントリ数が140くらいならbtreeの方が速い
という結果なりました。

グラフにするとこんな感じ。
(量が多すぎてグラフが書けなかったので先頭200回を取り出してます)

first200


サンプル数を1000にするとこんな感じ。

1000


ちなみに、keyをkey1とかkey2とかの、1づつ増やしての測定なので
btreeのツリーには偏りがあるかもしれません。
もしかすると一方向リストと同じかも・・・

CDF・PDFにするとこんな感じ。

cdf_hash_and_btree_200


pdf_hash_and_btree_200


何割かは、hashが速いようですが
btreeの方が速いケースが多いようです。
PDFでの、btreeの二つ目の山は140(くらい)を超えてからの
hashより遅くなるパターンが現れています。

1000回だとこう。

cdf_hash_and_btree_1000


pdf_hash_and_btree_1000


140を超え、btreeがhashより遅くなるパターンが多いので
大体の場合、hashの方が速いようですね。

btreeの200回と1000回の比較はこれ。

hash_cdf_200and1000


hashの200回と1000回の比較。

hash_cdf_200and1000


200回のグラフが、速いケースが多いのは
恐らくツリーが膨れていないからでしょう。
1000回だと、ツリーが大きくなって
時間のかかるケースの割合が増えるからでしょうか。

btreeの200回と1000回の比較はこれ。

btree_pdf_200and1000


山の高さが見事に逆転していますね。

hashの200回と1000回の比較

hash_pdf_200and1000


山が低くなっていますね。
hashの衝突などで、極端に遅くなるケースも出てくるからでしょうか。

nanodayo at 00:33コメント(0)トラックバック(0) 
データベース 

トラックバックURL

コメントする

名前
 
  絵文字