ホーム ] TIPS ウィンドウズ系 ] TIPS グラフィックス系 ] TIPS メルチメディア系 ] TIPS 理数系 ] TIPS 総覧 ]

上へ
S0001 数式処理
S0002 数式演算
S0003 陰関数のグラフ
S0004 モンテカルロ法
S0005 最小自乗法
S0006 高速冪乗算
S0007 正規乱数
S0008 相関係数
S0101 高速ソート
S0102 高速検索

VB.NET2005 TIPS / 理数系

S0102 高速検索

最終更新:2006/11/12 新規

●解説

 配列やオブジェクト集団から任意の値を探し出す方法である。ここでは値空間が不連続なものを対象にしている(連続なら検索に及ばない)。最も遅いのは、配列にて、ランダムに並んだ要素を逐次比較で探す方法となる。ここではそれ以外の速い方法を紹介する。

●原理

○バイナリサーチ

 最も一般的な方法である。この場合、値は予めソートされている必要がある。

○ハッシュテーブル

 不連続なコード(値)空間を一定の連続数値空間に圧縮変換する技法である。項目数が多ければ多いほど、バイナリサーチなどより高速化が期待できるものである。

●方法

○バイナリサーチ

 これは、自分でコード化するまでもなく、Arrayクラスのメソッドとなっているので、それを利用する。

   Array.BinarySearch(SomeArray)

である。元の配列が二次元なら、一次元のキー配列を抜き出せば良い。また、ソートもSort メソッドで行える。

○ハッシュテーブル

 これを、自分でコード化すると難しくなるので、ハッシュテーブルクラスを利用する。ハッシュテーブルは配列でなく、コレクションの一種で、配列より高速処理が期待でき、また使用方法が簡単である(コレクションの基本的なメソッドが準備されている)。

 一般に、Keyオブジェクトとそれに対応するValueオブジェクトからなる。Keyは任意の文字列など、Valueは値、構造体、クラスなどである。 圧縮変換で生じたかち合い(コリジョン)は内部で適宜処理されるので、気にしなくて良い。

 Dim HT As New System.Collections.Hashtable()      '空白のハッシュテーブルが生成される

 HT.Add(Keyi, Vi)

にて、KeyiでViを関連付け、

 HT.Item(Keyi)

にて、Vi を参照できる。自分で配列を生成したり、高速ソートを使用してマージする処理が全く不要となる。

 テーブルを総なめする処理は、Keyコレクションを利用して、

Dim k As Object
For Each k In HT.Keys
   Dim V As XXXXXX = HT.Item(k)                 'XXXXXX はValueのオブジェクト型
   ・・・・・・・
   ・・・・・・・
Next

などとする。

 Valueの更新は、

HT.Item(Keyi) = Vnew

でできる。

●ハッシュテーブル事例

 同じ値がないと分っている名簿を使って、任意の氏名を探す例。

 Dim Meibo(c - 1, Cnt - 1) As Object   '既にある名簿、0 列が氏名とする。

Cnt は例えば数万以上

・初期設定

Dim HT As New HashTable

For i = 0 To Cnt - 1
   HT.Add(CStr(Meibo(0, i)), i)           '氏名をKey にし、インデックスをValue とする。
Next

・参照

Simei が探す氏名、Ix をインデックスとすれば、

Dim Obj As Object = HT.Items(Simei)
If Obj IsNot Nothing Then
   Ix = CInt(Obj)
Else
   Ix = -1
End If