- PR -

ハッシュテーブルの検索速度について

«前のページへ 1|2
投稿者投稿内容
moondog
大ベテラン
会議室デビュー日: 2003/04/11
投稿数: 165
投稿日時: 2004-08-19 13:51
＝＝＝＞todo様

レス、ありがとうございます。

＞読み込んだデータテーブルのPrimaryKeyを設定して、
.Rows.Findで検索するという手をよく使います。

これは今回のようにあらかじめデータをテーブルに格納しておくのではなく、
コードの走査時にデータベースを読んでFindするということですよね？

今回のように走査する件数が少ない場合にはＤＢアクセスに絡む
オーバヘッドの方が大きいのではないかと思うのですが
そんなこともないのでしょうか。
todo
ぬし
会議室デビュー日: 2003/07/23
投稿数: 682
投稿日時: 2004-08-19 14:11
引用:

moondogさんの書き込み (2004-08-19 13:51) より:
＞読み込んだデータテーブルのPrimaryKeyを設定して、
.Rows.Findで検索するという手をよく使います。

これは今回のようにあらかじめデータをテーブルに格納しておくのではなく、
コードの走査時にデータベースを読んでFindするということですよね？

いいえ。
あらかじめデータをテーブル(DataTable)に格納してPrimaryKeyを設定しておく。
コードの走査時に
テーブル.Rows.Find(キー) != null
で存在チェックが出来る。

50件程度ならわざわざ別のインデックスを用意する価値はあんまりない

という意見でした。
moondog
大ベテラン
会議室デビュー日: 2003/04/11
投稿数: 165
投稿日時: 2004-08-19 14:36
＝＝＝＞なちゃ様

レスありがとうございます。

＞40回程度の検索で、1秒の差が出るということはまず考えられません。
確かに。^^;

今回の測定箇所は、純粋にループの前後ではないのですが、
これ以外のコードは不変なので、この２つのロジックの
違いによるスピード差であると結論づけてしまったのですが…

ちなみに、測定したコードの概要を下記に掲載します（変数の定義等は一部省略します）。

Dim tm_start As Date
Dim tm_end As Date

tm_start = Now '①システム時刻をセット
sSQL = "SELECT CODE FROM TBL_TEST"
Try
　　cmd_test.CommandText = sSQL
　　dr_test = cmd_test.ExecuteReader()
　　While dr_test.Read
　　　　'②ここを４０回通過
　　　　chk_code = dr_test.Item(0)
　　　　sw_hit = False　
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
　　　　if ht_Master.ContainsKey(chk_code) = Then 'テストケース１
　　　　　　'マスタに存在した場合の処理
　　　　End if
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
　　　　For i = 0 To Master_Ctr - 1　'テストケース２
　　　　　　'③ここを１３２８回通過
　　　　　　If chk_code = Tbl_Master(i).code Then
　　　　　　　　sw_hit = True
　　　　　　　　Exit For
　　　　　　End If
　　　　Next
　　　　If sw_np = True Then
　　　　　　'マスタに存在した場合の処理
　　　　End If
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
　　End While
Catch ex As Exception
　　'エラー処理
End Try
dr_test.Close()
tm_end = Now '④システム時刻をセット

MsgBox("tm_start = " & tm_start)
MsgBox("tm_end = " & tm_end)

とういう具合に表示した時刻の差が配列読みだと平均１５秒、
ハッシュだと平均１６秒でした。（５回ぐらいやった平均）
で、実際には”マスタに存在した場合の処理”でテーブルに格納したり
しているのですが、テストケース１、２以外の箇所のコードは同じですので
この２つの検索方法の違いが速度の違いであると判断しました。

もしかしてミリ秒単位まで表示すべきだったのかな？
実際には数ミリ秒の差だったのかもしれません。^^;

しかし、今回のケースでは配列読みの方が速かったというのは事実です。
moondog
大ベテラン
会議室デビュー日: 2003/04/11
投稿数: 165
投稿日時: 2004-08-19 14:43
＝＝＝＞Jitta様

レスありがとうございます。

＞検索対象が“昇順に並んでいる”のなら、クイックサーチや二分木サーチという手があります。検索されるデータの偏りにも因りますが、シーケンシャルサーチよりも早いことが期待されます。

イタイところを突かれました。^^;
おっしゃる通りです。

検索アルゴリズムを勉強して出直してきます。
moondog
大ベテラン
会議室デビュー日: 2003/04/11
投稿数: 165
投稿日時: 2004-08-19 14:45
＝＝＝＞todo様

レスありがとうございます。

ご教示頂いた方法でも実装してみて速度を比較してみようと思います。

アドバイスありがとうございました。
moondog
大ベテラン
会議室デビュー日: 2003/04/11
投稿数: 165
投稿日時: 2004-08-19 16:40
お世話さまです。

todo様からアドバイス頂いたDataTableを用いた実装が実現したので、
シーケンシャル、ハッシュ、プライマリキーの３種類それぞれ５回づつ実行して
実行速度を比較検証してみました。

実装方法については自信がないのでご参考までに掲載致します。^^;

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
Dim myDataSet As DataSet
Dim myDataTable As DataTable = New DataTable("MasterTable")
Dim myDataColumn As DataColumn
Dim myDataRow As DataRow
Dim PrimaryKeyColumns(0) As DataColumn

myDataColumn = New DataColumn
myDataColumn.DataType = System.Type.GetType("System.String")
myDataColumn.ColumnName = "code"
myDataColumn.ReadOnly = True
myDataColumn.Unique = True
myDataTable.Columns.Add(myDataColumn)

PrimaryKeyColumns(0) = myDataTable.Columns("code")
myDataTable.PrimaryKey = PrimaryKeyColumns
myDataSet = New DataSet
myDataSet.Tables.Add(myDataTable)

'走査用マスタデータ読み込み
…
While dr_test.Read
　　myDataRow = myDataTable.NewRow()
　　myDataRow("code") = RTrim(dr_test.Item(0))
　　myDataTable.Rows.Add(myDataRow)
End While

…
if myDataTable.Rows.Find(chk_code) Is Nothing Then
Else
　　'マスタに存在した場合の処理
End If
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

今回はミリ秒単位まで計測して５回の平均値を取りました。
その結果…
①シーケンシャルリード：8,229（単位：ミリ秒）
②ハッシュ：8,174
③DataTable：8,238

となり、ハッシュが一番高速という結果でした。
しかもハッシュは５回とも速度が安定していました。

ちなみに、最速値と最遅値の差は下記のようになりました。
①シーケンシャルリード：211（単位：ミリ秒）
②ハッシュ：90
③DataTable：150

今回のテスト環境としましては
テストマシン（クライアント）：Win Xp Professional Edition
ＤＢサーバ：Win2003+SQL Server2000

ＤＢサーバはテスト用マシンで、私１人で専有的に使用してましたので、
外的影響を受ける可能性は低かったと思います。
（社内ネットワークトラフィックによる影響はあったかとは思いますが…）

それと、全１５回の計測結果に大きな変動がなかったことからも
比較環境は安定した状態に保てたのではないかと思います。
«前のページへ 1|2

スキルアップ／キャリアアップ（JOB@IT）