- - PR -
ハッシュテーブルの検索速度について
| 投稿者 | 投稿内容 | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
投稿日時: 2004-08-19 10:47
お世話さまです。
今回はトラブルシューティングというよりも問題提起に近いのですが、 ハッシュテーブルと通常のテーブルのシーケンシャルリードとの 速度比較についてお伺いしたく。 ．ＮＥＴ ＴＩＰＳの過去の記事を読んでいてハッシュテーブルなるモノ の存在を知り、シーケンシャルリードしているコードを置き換えて 実行速度を比較してみたところ、ハッシュの方がやや遅かったのです。 コードは下記のようなモノです。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ （シーケンシャルテーブルによるサーチ） Public Structure Master '存在チェック用配列 Public code As String End Structure Public Tbl_Master() As Master ＤＢ読み込みのコードは割愛しますが、この配列に５０件のデータを格納します。 Dim sw_hit As Boolean 'マスタの存在判定用 Dim chk_code As String '走査したいコードの格納用 Dim i As Short sw_hit = False For i = 0 To Master_Ctr - 1 'Master_Ctrには50が入ってます。 If chk_code = Tbl_Master(i).code Then sw_hit = True Exit For End If Next if sw_hit = True Then '存在していた場合の処理 End if ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ （ハッシュテーブルによるサーチ） Public ht_Master As Hashtable = New Hashtable '存在チェック用ハッシュ このテーブルにも５０件のデータを格納します。 Dim chk_code As String '走査したいコードの格納用 Dim i As Short if ht_Master.ContainsKey(chk_code) = Then '存在していた場合の処理 End if ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ で、５０件程度の件数では大したスピード差は得られないと考え、 上記２つの処理を相当数ループさせて比較したところ 後者のハッシュを使った走査の方が平均約１秒程度も遅かったのです。 走査するテーブルの格納数が大きくなればなるほどハッシュを使った方が 速くなるのかな？とは思っているのですが、実際のところ 件数と速度のトレードオフってどんなカンジなのでしょうか？ とりあえず今回の処理ではハッシュを使うのは断念しようと思っています。 | ||||||||||||
|
投稿日時: 2004-08-19 11:05
探索方法には得意・不得意があります。
線形な探索の場合、性能はデータの並び方に直接依存します。 例として、同じ500000個で、線形な探索で3を探す場合、 ・1,2,3,……,500000 ・500000,499999,499998,……,1 とでは大幅に性能が違います。前者はあっという間に終わりますが、後者は時間がかかります。 それに対し、ハッシュテーブルの場合、データの並び方で異なるということはないでしょう(同じハッシュ値のキーがどの程度あるか、に依存するはず)。 ともかく、データが分からない以上、単純にどちらが良いかという比較にはなりません。 [ メッセージ編集済み 編集者: ぢゃん♪ 編集日時 2004-08-19 11:10 ] | ||||||||||||
|
投稿日時: 2004-08-19 11:17
私は実際の検索パフォーマンスを検証したことはないのですが、まずはいくつか。 ・（特に値型の）配列は、コレクションとして扱う中では、操作自体は最速なものです。ですので、単純な操作に関して最も効率が良いのは確かです。 ・検索以外の処理は、パフォーマンスの測定時は何も影響は無しでしょうか？ ・相当数のループとは具体的にどの程度でしょう？また、約１秒程度の差とは、何秒程度対何秒程度なのでしょう？（差は何%程度？） ・繰り返す際に、検索対象のキーはランダムに決めていますか？配列の場合は順サーチですから、格納位置によってパフォーマンスは単純に変わります。一方、Hashtableの場合はそういう概念はまあないといってよいでしょう。 ある程度数が多くなれば、Hashtableの方がパフォーマンスは高くなるでしょう。 ただし、ある程度の数がどの程度なのかは私もつかんでいませんし、検索の特長に拠るでしょう。 他にも、データを格納する際に個数が確定していないといけないなど、配列を使う故に増える面倒があります。 コレクションクラスは、これらの機能、パフォーマンス、使い方の特徴などから、どれを使用するか、また配列でやってしまうのか決めるものだと思います。 ※Hashtableは、パフォーマンスだけが利点ではないということです。 内部的に見れば、Hashtableの検索ではハッシュ値の計算等が必要になりますので、追加の固定負荷は当然配列よりはずっと大きくなります。この固定負荷が、配列をサーチする負荷よりも小さくなるまで個数が増えれば、Hashtableの方がパフォーマンスがあがるでしょう。 [ メッセージ編集済み 編集者: なちゃ 編集日時 2004-08-19 11:21 ] | ||||||||||||
|
投稿日時: 2004-08-19 11:34
＝＝＝＞ぢゃん♪様
早速のレス、ありがとうございます。 ＞ともかく、データが分からない以上、単純にどちらが良いかという比較にはなりません。 ですよね。^^; 今回のは走査用マスタの５０件のデータは００１〜９９９の間の値で、 それを昇順に格納し、走査元のコードは同じく００１〜９９９の 範囲の値なんですが全くランダムに発生する、というものでした。 | ||||||||||||
|
投稿日時: 2004-08-19 11:47
＝＝＝＞なちゃ様
早速のレス、ありがとうございます。 ＞・検索以外の処理は、パフォーマンスの測定時は何も影響は無しでしょうか？ 影響無しで比較できたと思います。 ＞・相当数のループとは具体的にどの程度でしょう？ 実は実際のＤＢ読み込みのループの中で比較したので、 恣意的・固定的に１万回ループとかの比較ではなかったのですが、 カウンタを入れてトレースしてみましたところ ハッシュによる総検索回数は４０回で、 シーケンシャルリードのForループ内の回数は１３２８回でした。 （少なくともハッシュによる検索も数百回は回ってるものと錯覚してました。^^;） ＞また、約１秒程度の差とは、何秒程度対何秒程度なのでしょう？（差は何%程度？） このＤＢの全件読み込みの前後で計測したのですが、 配列を使った場合が１５秒でハッシュと使った場合が１６秒でした。 ＞一方、Hashtableの場合はそういう概念はまあないといってよいでしょう。 確かにそういう期待はできますね。 ＞内部的に見れば、Hashtableの検索ではハッシュ値の計算等が必要になりますので、追加の固定負荷は当然配列よりはずっと大きくなります。この固定負荷が、配列をサーチする負荷よりも小さくなるまで個数が増えれば、Hashtableの方がパフォーマンスがあがるでしょう。 勉強になりました。 ご教示ありがとうございました。 | ||||||||||||
|
投稿日時: 2004-08-19 12:31
読み込んだデータテーブルのPrimaryKeyを設定して、.Rows.Findで検索するという手をよく使います。
コードが簡潔であり、パフォーマンスは測定したことはないが50件なら問題ないでしょう。 | ||||||||||||
|
投稿日時: 2004-08-19 12:52
ちょっと疑問なんですが… ハッシュの検索回数は40回で、配列の検索自体も40回、配列の検索の際にループで回った総回数が1328回ということですよね？ もちろんマシンのスペックやらその他に依存しますが、40回程度の検索で、1秒の差が出るということはまず考えられません。 コードがないと分かりませんが、例えばすごく無駄な検索を内部で繰り返しているとか、構造体のサイズがかなり大きいとか、ボクシングとアンボクシングを大量に繰り返しているとか、何かおかしな部分がないですか？ | ||||||||||||
|
投稿日時: 2004-08-19 13:22
とりあえず、ここだけに注目。 検索対象が“昇順に並んでいる”のなら、クイックサーチや二分木サーチという手があります。検索されるデータの偏りにも因りますが、シーケンシャルサーチよりも早いことが期待されます。
各検索方法のアルゴリズムを正しく理解しており、今回行う検索の内容にっては、この言葉は正しいかもしれません。 しかし、
という言葉、および、並び替え済みのデータを検索にシーケンシャルサーチを使うことから、検索アルゴリズム全体が理解できていないと思われます。この辺に、他の方々の「ちょっと待て」の原因があると思います。 | ||||||||||||
スキルアップ／キャリアアップ（JOB@IT）
Copyright © ITmedia, Inc. All Rights Reserved.
著作権はアイティメディア株式会社またはその記事の筆者に属します。
当サイトに掲載されている記事や画像などの無断転載を禁止します。
著作権はアイティメディア株式会社またはその記事の筆者に属します。
当サイトに掲載されている記事や画像などの無断転載を禁止します。