|
ソフトウェア実験室 |
|
検索速度 |
| 最終更新：2005/12/11 修正 |
VB.NETで検索方法やデータ量による速度を比較する。
●比較対象
○検索方法による違い
・逐次比較法
・バイナリサーチ法
・ハッシュテーブル法
について、データ型を変化させる。
○データ量による違い
バイナリサーチ法とハッシュテーブル法にて検索テーブル長を変える。
●比較・実験方法
データ型は、Long、Double、String
の三種類とし、一次元のObject型配列に非連続空間で生成する。但し、昇順で並べる。検索キーは、その配列より、予め満遍なく選んでおく(従って、不一致はない)。初期のテーブル生成や、ハッシュテーブル生成の時間は計測時間に含めない。
→注意：テーブル長が余りに大きいと、実行時、仮想記憶が生起され正確な時間測定ができなくなるので、マシンの仕様に合わせて設定する必要がある。
○検索方法による違い
三つの検索方法、三つのデータ型の計9通り計測する。テーブル長は、5万データ、検索キーは5千種とし、全検索時間を測定する。
○データ量による違い
テーブル長を、10万から100万の5種にて、検索キーを5万種にて計測する。データ型はString。
●結果
いずれもマシンは、CPU：ペンティアム4 2GHz、メモリ：1024MB、OS：Windows XP Pro SP2 となっている。
○検索方法による違い
単位：ms
ハッシュテーブル法は計測不能。
○データ量による違い
単位：ms
●考察
いずれも、絶対時間は意味がなく、互いの比較に意味がある。
○検索方法による違い
検索方法による比較のための演算数は、テーブル長を N とすれば、
| 方法 | 演算数 | 備考 |
| 逐次比較法 | N/2 | ソート済での平均値 |
| バイナリサーチ法 | log2N | ソートが必須 |
| ハッシュテーブル法 | h(一定) | f(Key)なる変換演算数 |
となる。逐次比較では、ソートされていないと、不一致の場合、常にN回の演算が必要となり、最悪となる。基本的に使わないのが賢明である。ハッシュテーブル法では、シノニムがなければ、等速検索になると期待される。
○データ量による違い
上表のように、ハッシュテーブル法では、テーブル長による違いは余り見られない。ハッシュテーブル法はバイナリサーチ法の約10倍くらいの速度。
●結論
- 非連続空間のキーの検索では、ハッシュテーブル法が圧倒的に速い。しかも、原理的にデータ型やテーブル長、ソートの有無に依存しないので、好都合であるし、基本機能は.NETにて整っているので活用しない理由はない。
- バイナリサーチ法も.NETにてメソッドとして提供されているので、簡単に利用できる。小、中規模のデータでの利用が良い。
●実験のプログラムリスト
(省略)