2011年02月15日
BDBで測定してみた
BDBで使えるデータ構造についてです。
BDB内の用語ではアクセスメソッドと呼ばれています。
行単位なデータ構造
多分双方向リストと変わらない・・・?
行番号みたいな概念があるので
BDBでも次のデータとか前のデータみたいな指定の仕方ができます。
順番に処理したい時には適しているデータ構造ですね。
いわゆる二分木ツリー。
図にするとこんな感じ。
ツリーの偏りが控えめに構築できていれば
パフォーマンスは良いはず。
オーダーはLog Nとかになるんだったかな。
一定の法則に基づいて、元の値に対するインデックスの値を求めます。
割り算が例に出されることが多いです。
例えばある数を、9で割った余りは0から8のどれかになります。
これをそのまま配列の添字にして格納すれば探索が一回でできるので
データの量と関係なく、一定の速度が期待できます。
これがkey-valueのペアだったりすると
keyに対応するvalueを一回の処理で探索できます。
ところが、ここで疑問が出てくると思います。
元の値は違うけど、たまたま同じハッシュ値になったらどうするんだろうと
そう、確かにそういう問題がはらんでいます。
なので
・ハッシュ値の範囲を広くする
・衝突した場合、そこにリストを作って管理する
という方法が採られています。
リストの例は、図の8番目の配列がそうですね。
衝突した場合は別ですが
エントリ数が多くても、検索にかかる処理は同じなので
大量のエントリを扱う場合はハッシュが適しているかと思います。
ただし、使われないメモリ領域も確保する必要があるので
無駄が生じます。
図で言うと2,5,8以外は使っていませんしね。
このように、データ構造ごとに特徴がありますが
実際、性能の差はどんなものだろうということで測定してみました。
内容としてはスクリプトを使って
100000回くらいDBへのPUTを実行し
一回一回のPUTにかかった時間を測定してみました。
結果としては
グラフにするとこんな感じ。
(量が多すぎてグラフが書けなかったので先頭200回を取り出してます)
サンプル数を1000にするとこんな感じ。
ちなみに、keyをkey1とかkey2とかの、1づつ増やしての測定なので
btreeのツリーには偏りがあるかもしれません。
もしかすると一方向リストと同じかも・・・
CDF・PDFにするとこんな感じ。
何割かは、hashが速いようですが
btreeの方が速いケースが多いようです。
PDFでの、btreeの二つ目の山は140(くらい)を超えてからの
hashより遅くなるパターンが現れています。
1000回だとこう。
140を超え、btreeがhashより遅くなるパターンが多いので
大体の場合、hashの方が速いようですね。
btreeの200回と1000回の比較はこれ。
hashの200回と1000回の比較。
200回のグラフが、速いケースが多いのは
恐らくツリーが膨れていないからでしょう。
1000回だと、ツリーが大きくなって
時間のかかるケースの割合が増えるからでしょうか。
btreeの200回と1000回の比較はこれ。
山の高さが見事に逆転していますね。
hashの200回と1000回の比較
山が低くなっていますね。
hashの衝突などで、極端に遅くなるケースも出てくるからでしょうか。
BDB内の用語ではアクセスメソッドと呼ばれています。
recno
行単位なデータ構造
多分双方向リストと変わらない・・・?
行番号みたいな概念があるので
BDBでも次のデータとか前のデータみたいな指定の仕方ができます。
順番に処理したい時には適しているデータ構造ですね。
btree
いわゆる二分木ツリー。
図にするとこんな感じ。
ツリーの偏りが控えめに構築できていれば
パフォーマンスは良いはず。
オーダーはLog Nとかになるんだったかな。
hash
一定の法則に基づいて、元の値に対するインデックスの値を求めます。
割り算が例に出されることが多いです。
例えばある数を、9で割った余りは0から8のどれかになります。
これをそのまま配列の添字にして格納すれば探索が一回でできるので
データの量と関係なく、一定の速度が期待できます。
これがkey-valueのペアだったりすると
keyに対応するvalueを一回の処理で探索できます。
ところが、ここで疑問が出てくると思います。
元の値は違うけど、たまたま同じハッシュ値になったらどうするんだろうと
そう、確かにそういう問題がはらんでいます。
なので
・ハッシュ値の範囲を広くする
・衝突した場合、そこにリストを作って管理する
という方法が採られています。
リストの例は、図の8番目の配列がそうですね。
衝突した場合は別ですが
エントリ数が多くても、検索にかかる処理は同じなので
大量のエントリを扱う場合はハッシュが適しているかと思います。
ただし、使われないメモリ領域も確保する必要があるので
無駄が生じます。
図で言うと2,5,8以外は使っていませんしね。
測定してみた
このように、データ構造ごとに特徴がありますが
実際、性能の差はどんなものだろうということで測定してみました。
内容としてはスクリプトを使って
100000回くらいDBへのPUTを実行し
一回一回のPUTにかかった時間を測定してみました。
結果としては
- ハッシュは極端に遅いケースがあるが安定している
- エントリ数が140くらいならbtreeの方が速い
グラフにするとこんな感じ。
(量が多すぎてグラフが書けなかったので先頭200回を取り出してます)
サンプル数を1000にするとこんな感じ。
ちなみに、keyをkey1とかkey2とかの、1づつ増やしての測定なので
btreeのツリーには偏りがあるかもしれません。
もしかすると一方向リストと同じかも・・・
CDF・PDFにするとこんな感じ。
何割かは、hashが速いようですが
btreeの方が速いケースが多いようです。
PDFでの、btreeの二つ目の山は140(くらい)を超えてからの
hashより遅くなるパターンが現れています。
1000回だとこう。
140を超え、btreeがhashより遅くなるパターンが多いので
大体の場合、hashの方が速いようですね。
btreeの200回と1000回の比較はこれ。
hashの200回と1000回の比較。
200回のグラフが、速いケースが多いのは
恐らくツリーが膨れていないからでしょう。
1000回だと、ツリーが大きくなって
時間のかかるケースの割合が増えるからでしょうか。
btreeの200回と1000回の比較はこれ。
山の高さが見事に逆転していますね。
hashの200回と1000回の比較
山が低くなっていますね。
hashの衝突などで、極端に遅くなるケースも出てくるからでしょうか。