ハッシュテーブルの検索について
お世話になります。卓郎と申します。
VB.NETでハッシュテーブルを作成しているのですが、
索方法についてお聞きしたく書き込みいたしました。
キーはコード１０桁+任意４桁です。
"12345678901111"
"12345678902222"
"12345678903333"
"11111111111111"
"11111111112222"
"11111111113333"
こういったキーを持つデータが３０万件以上あります。
この中でコード１０桁が"1234567890"の値をすべて抽出したいのですが、
現在はハッシュテーブルの名前をhashTestとした場合、
For Each ht As DictionaryEntry In hashTest
if Mid(ht.Key, 1, 10) = "1234567890"
'値の出力
end if
Next
としているのですが、これだとものすごく時間がかかってしまいます。
もしよい方法があれば教えていただけないでしょうか？
よろしくお願い致します。
今のままでは、データを列挙するしかないかと。
思い切って、データの保持構造を見直してみては?
たとえば、10桁部だけを持ったHashTable内に、
14桁部のHashTableを階層的に保持させて
├"1234567890"
│├"12345678901111"
│├"12345678902222"
│└"12345678903333"
├"1111111111"
│├"11111111111111"
│├"11111111112222"
│└"11111111113333"
のような構造にしておけば、「コード10桁」での検索は容易かと。
For Each entry14 As DictionaryEntry In Hash10("1234567890")
'値の出力
Trace.WriteLine(entry14.Value)
Next
Hashtableでは無くSortedListを使ったらどうかな。
卓郎です。
＞Dentalさん
このような持ち方できるんですか？
たとえば14桁のキーを持ったハッシュテーブルをHash14,
たとえば10桁のキーを持ったハッシュテーブルをHash10
とした場合、
hash14.add("12345678901111",'あああ')
hash14.add("12345678902222",'あああ')
hash14.add("12345678903333",'あああ')
となり、
hash10に"1234567890"をキーとして今あげたhash14の値を
格納すると言うことですよね。
この場合、Hash10にhash14を加えるのはどうすればよいのでしょうか？
＞ねろさん
SortedList、聞いたことなかったので今調べています。
参考になる意見、ありがとうございます。
作ってみました。
元の hashTest("12345678901111") が、どのような値を返すのか
わからなかったので、とりあえず キー＝値にしてあります。
Dim Hash10 As New Hashtable
Hash10.Add("1234567890", Hash14("12345678901111", "12345678902222", "12345678903333"))
Hash10.Add("1111111111", Hash14("11111111111111", "11111111112222", "11111111113333"))
For Each ht As DictionaryEntry In Hash10("1234567890")
'値の出力
Trace.WriteLine(ht.Value)
Next
'---------------
Function Hash14(ByVal ParamArray X() As String) As Hashtable
Hash14 = New Hashtable
For Each s As String In X
Hash14.Add(s, s)
Next
End Function
卓郎です。
＞魔界の仮面弁士さん
わざわざ作っていただき、ありがとうございます。
Hash10.Add("1111111111", Hash14("11111111111111", "11111111112222", "11111111113333"))
のところですが、やっぱりHash14のキーを羅列しないといけないのでしょうか？
たとえばhash14を全部読み込んだ後、たとえばHash14のキー先頭１０バイトが"1111111111"の場合、hash10の"1111111111"の値とするというようなことは出来ないのでしょうか？
わかりづらくて申し訳ありません。
先の回答は、「全部を列挙して探し出す手法」だと効率が悪すぎるので、
データの格納形式を見直して、「10桁」のコードでも検索しやすいような
作り方をする必要があるでしょう。。。という話になっていますよね?
でもって、その格納形式の提案として、HastTable を使って階層的に
管理する、という手法を提案したわけですが。
まず、ここまでの点で何か問題はありますか?
もしもデータの格納形式を変更できないようであれば、この話は
振り出しに戻ってしまうわけですが。。。
> Hash14のキーを羅列しないといけないのでしょうか？
それは、「6件のサンプルデータ」を作っている部分なので、
『データの検索』という処理とは、直接は関係無いような。
もちろん、『階層データを作成』するためには、最終的には30万件分の
データを登録するために、30万回(あるいはそれ以上)のキー登録が
必要ですが、それは先の Hash14 なサンプルであれ、最初に卓郎さんが書いた
> For Each ht As DictionaryEntry In hashTest
> if Mid(ht.Key, 1, 10) = "1234567890"
> '値の出力
> end if
> Next
という「hashTest」という変数を使った既存のプログラムでも同じこと、ですよね?
# そもそも、元のデータがどこから得られるのかも不明なので、これ以上はどうにも。
# 「30万件」の元データが、最初から Hashtable形式で渡されるのか、
# データベースやファイル等で渡されるのか……あるいは、測定器等から
# 少しずつ送られてくるのかなど、データの受け渡し方によっては、
# もしかしたら適切な手法が変わるかも知れないわけで。
> たとえばhash14を全部読み込んだ後、たとえばHash14のキー先頭１０バイトが
> "1111111111"の場合、hash10の"1111111111"の値とするというようなことは
> 出来ないのでしょうか？
質問の意図がよくわからないのですが……早い遅いではなく、出来るか出来ないかと
問われるのであれば、技術的には「できる」という答えになるでしょうけれどね。
最終的に、それを実際に作れるかどうかは、卓郎さんの力量次第という事になるような。
たとえば、管理しやすくするために、HashTable を継承した独自のクラスを作り、
そこに、各データを(先に提示したように)「階層化」して持たせる事や、さらに
そのクラスに、データの登録や検索を行うメソッドを持たせてみても良いでしょう。
(階層化した場合の検索の方法などは、既にサンプルが提示されているのですし)
もしくは、既に提案されていた SortedList を使ってみるのであれば、
データがソートされて格納される事を利用して。。。こんな感じかなぁ。
=====================
Dim X As New SortedList
'--- サンプルデータ ---
X.Add("1234567890", "") 'データの作成時には、検索用に「10桁部」だけの
X.Add("1111111111", "") '情報も、一緒に格納しておくようにする。
X.Add("12345678901111", "あ")
X.Add("11111111112222", "い")
X.Add("12345678903333", "う")
X.Add("11111111111111", "え") 'これらは、SortedList内に
X.Add("11111111113333", "お") '格納される際に、キー順に
X.Add("12345678902222", "か") 'データが並び替えられる。
'--- 検索 ---
Trace.WriteLine("先頭が 1234567890 の物")
For Each V As String In Search(X, "1234567890")
Trace.WriteLine(V)
Next
Trace.WriteLine("先頭が 1111111111 の物")
For Each V As String In Search(X, "1111111111")
Trace.WriteLine(V)
Next
=====================
Private Function Search(ByVal List As SortedList, ByVal SearchWord As String) As ArrayList
'「10桁」だけのデータの位置を探す
Dim Position As Integer = List.IndexOfKey(SearchWord)
Search = New ArrayList
If Position >= 0 Then
'10桁だけのデータが見つかったら、その次の位置から検索開始
For Index As Integer = Position + 1 To List.Count - 1
Dim Key As String = CStr(List.GetKey(Index))
If Key.StartsWith(SearchWord) Then
'先頭部が一緒なら、戻り値に追加
Search.Add(List.GetByIndex(Index))
Else
'先頭部が異なれば、列挙終了
Exit For
End If
Next
End If
End Function
SortedListについて調べられましたか。
こうしたサーチはデーターをソートして、２分木検索で検索を行うと相場は決まっています。
SortedListはKeyでソートしてくれますのでKeyを２分木検索で検索すればいいのです。
下は簡単なサンプルです（エラーの処理など全て省略してあります、最近やけに突っ込まれるので・・）
実際は１４文字を１０文字で２分木検索してありますので、検索の結果は複数ヒットするはずですが、
実際は最初のヒットしたindexを返します、従って該当のデーターのどこに落ちるかは確定しませんが、
検索で帰ってくるindexの上と下のKeyの前の１０文字を一致しなくなるまで探せば良いことになります。
(とりあえずこの部分は省略)
検索は高速です。確認の為、ListBoxとTextBoxを置いています。
Dim MySotedList As New SortedList
Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
MySotedList.Add("12345678901111", "12345678901111D")
MySotedList.Add("12345678902222", "12345678902222D")
MySotedList.Add("12345678903333", "12345678901111D")
MySotedList.Add("11111111111111", "11111111111111D")
MySotedList.Add("11111111112222", "11111111112222D")
MySotedList.Add("11111111113333", "11111111113333D")
MySotedList.Add("22222222221111", "22222222221111D")
MySotedList.Add("22222222222222", "22222222222222D")
MySotedList.Add("22222222223333", "22222222223333D")
For i As Integer = 0 To MySotedList.Keys.Count - 1
ListBox1.Items.Add(MySotedList.GetKey(i))
Next
End Sub
Public Function BinarySearch(ByVal DataStart As Integer, ByVal DataEnd As Integer, ByVal Data As String) As Integer
'１０文字の二分木検索
Dim DataIndex As Integer
While (DataStart <= DataEnd)
DataIndex = CType(DataStart + (DataEnd - DataStart) / 2, Integer)
Dim s1 As String = CType(MySotedList.GetKey(DataIndex), String).Substring(0, 10)
Dim s2 As String = Data.Substring(0, 10)
If String.Compare(s1, s2) > 0 Then
DataEnd = DataIndex - 1
ElseIf String.Compare(s1, s2) < 0 Then
DataStart = DataIndex + 1
Else
Return (DataIndex)
End If
End While
End Function
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim t As Integer = BinarySearch(0, MySotedList.Keys.Count - 1, "2222222222") 'データーサーチ
'TextBox1.Text = CType(MySotedList.GetKey(t), String) 'Keyを表示
TextBox1.Text = CType(MySotedList.Item(MySotedList.GetKey(t)), String) 'データーを表示
End Sub
あー！
>Dim s1 As String = CType(MySotedList.GetKey(DataIndex), String).Substring(0, 10)
>Dim s2 As String = Data.Substring(0, 10)
Dim s1, s2 As String
While
・・
s1 = CType(MySotedList.GetKey(DataIndex), String).Substring(0, 10)
s2 = Data.Substring(0, 10)
宣言はWhileの外に出してください。orz
チョンボ多いな。。。
卓郎です。
皆さん、いろいろとアドバイスありがとうございます。
Dentalさんのおっしゃるようにもうちょっと詳しく書くべきですね。
すみません。
データはテキスト(TSV)から読み込みます。
12345678901111 あああ
11111111111111 えええ
12345678902222 いいい
11111111112222 おおお
12345678903333 ううう
11111111113333 かかか
こういう形で、さっき正確に件数を見たら１００万件程ありました。
これを、ハッシュテーブルなどに読み込み、
たとえばキーの先頭１０バイトが"1234567890"のデータをすべて
抽出する、と言う風な処理を行いたいのです。
ハッシュテーブルだと、TSVファイルから全件格納するのは３分くらい
で終わるのですが、キーの先頭１０バイトに該当するデータを
抽出する処理に時間がかかってしまいます。
この処理が、スムーズに言ってくれることが一番の理想なんですが・・・。
また先程から、教えていただいたSortedListに格納しようとしてるのですが、
２時間たった今でもまだ処理が終わっていません・・・・。
どうにかスムーズに行う方法はありませんでしょうか？
100万件ですか、通常はデーターベースで処理でしょうが、
DosコマンドのFindで検索してリダイレクトでファイルに吐き出す手も有る。
データーがあまり変わらなければ、DosコマンドでSortして配列に入れ、
配列上で検索する手も有る。
Processクラスを使うとファイルにリダイレクトしなくても結果が取れるようです。
Dim FindString As String
Dim FileName As String
Dim myProcessStart As New System.Diagnostics.ProcessStartInfo
FileName = "c:\test.txt" '検索ファイル
FindString = "1111111111" '検索文字
With myProcessStart
.FileName = System.Environment.GetEnvironmentVariable("ComSpec")
.RedirectStandardInput = False
.RedirectStandardOutput = True
.UseShellExecute = False
.CreateNoWindow = True 'Window非表示
.Arguments = "/c type " & FileName & " | Find " & Chr(34) & FindString & Chr(34)
End With
Dim MyProcess As Process = Process.Start(myProcessStart)
FindString = MyProcess.StandardOutput.ReadToEnd '出力Read
Console.WriteLine(FindString) '検索結果
MyProcess.WaitForExit() '終了
これで遅かったらごめんなさい。
同時に、何か別の処理を行っていませんか?(画面更新とか)
もしくは、データに極端な偏りがあるとか。
実際に、200万レコードのTSVファイルを作って、先の回答にあった
「階層化されたHashtable」の手法で試してみましたが、
そんなに時間は掛からなかったのですが……。
PCスペックとデータのばらつき度合いにもよりますが、当方では、
『キーの先頭10バイトが"1234567890"のデータの列挙』は、
0.02秒〜0.8秒といったところでしたし、200万件のデータを
階層ハッシュ化するのも、12秒〜40秒程度で完了しました。
私の書いた、SotedListも1,000,000件ののデーターセットに
約１５秒、検索は0.5秒以下ですが。
もしかしてデバッグの為に付けた、ListBoxにデーターを
表示させてません？
ListBox1.Items.Add(MySotedList.GetKey(i))
これはやってはいけませんよ。
| ツイート |  |