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


卓郎  2005-08-24 20:54:44  No: 124382

お世話になります。卓郎と申します。
VB.NETでハッシュテーブルを作成しているのですが、
索方法についてお聞きしたく書き込みいたしました。

キーはコード10桁+任意4桁です。

"12345678901111"
"12345678902222"
"12345678903333"
"11111111111111"
"11111111112222"
"11111111113333"

こういったキーを持つデータが30万件以上あります。
この中でコード10桁が"1234567890"の値をすべて抽出したいのですが、
現在はハッシュテーブルの名前をhashTestとした場合、

For Each ht As DictionaryEntry In hashTest
   if Mid(ht.Key, 1, 10) = "1234567890"
       '値の出力
   end if
Next

としているのですが、これだとものすごく時間がかかってしまいます。
もしよい方法があれば教えていただけないでしょうか?
よろしくお願い致します。


Dental  2005-08-24 22:02:30  No: 124383

今のままでは、データを列挙するしかないかと。
思い切って、データの保持構造を見直してみては?

たとえば、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


ねろ  2005-08-24 22:17:09  No: 124384

Hashtableでは無くSortedListを使ったらどうかな。


卓郎  2005-08-24 22:34:25  No: 124385

卓郎です。

>Dentalさん

このような持ち方できるんですか?
たとえば14桁のキーを持ったハッシュテーブルをHash14,
たとえば10桁のキーを持ったハッシュテーブルをHash10
とした場合、
hash14.add("12345678901111",'あああ')
hash14.add("12345678902222",'あああ')
hash14.add("12345678903333",'あああ')
となり、
hash10に"1234567890"をキーとして今あげたhash14の値を
格納すると言うことですよね。
この場合、Hash10にhash14を加えるのはどうすればよいのでしょうか?

>ねろさん

SortedList、聞いたことなかったので今調べています。
参考になる意見、ありがとうございます。


魔界の仮面弁士  2005-08-24 22:55:30  No: 124386

作ってみました。

元の 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


卓郎  2005-08-24 23:21:37  No: 124387

卓郎です。

>魔界の仮面弁士さん

わざわざ作っていただき、ありがとうございます。
Hash10.Add("1111111111", Hash14("11111111111111", "11111111112222", "11111111113333"))

のところですが、やっぱりHash14のキーを羅列しないといけないのでしょうか?
たとえばhash14を全部読み込んだ後、たとえばHash14のキー先頭10バイトが"1111111111"の場合、hash10の"1111111111"の値とするというようなことは出来ないのでしょうか?
わかりづらくて申し訳ありません。


Dental  2005-08-25 04:13:03  No: 124388

先の回答は、「全部を列挙して探し出す手法」だと効率が悪すぎるので、
データの格納形式を見直して、「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のキー先頭10バイトが
> "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


ねろ  2005-08-25 07:11:31  No: 124389

SortedListについて調べられましたか。
こうしたサーチはデーターをソートして、2分木検索で検索を行うと相場は決まっています。
SortedListはKeyでソートしてくれますのでKeyを2分木検索で検索すればいいのです。
下は簡単なサンプルです(エラーの処理など全て省略してあります、最近やけに突っ込まれるので・・)
実際は14文字を10文字で2分木検索してありますので、検索の結果は複数ヒットするはずですが、
実際は最初のヒットしたindexを返します、従って該当のデーターのどこに落ちるかは確定しませんが、
検索で帰ってくるindexの上と下のKeyの前の10文字を一致しなくなるまで探せば良いことになります。
(とりあえずこの部分は省略)
検索は高速です。確認の為、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
        '10文字の二分木検索
        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


ねろ  2005-08-25 16:36:41  No: 124390

あー!
>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
チョンボ多いな。。。


卓郎  2005-08-25 20:29:51  No: 124391

卓郎です。
皆さん、いろいろとアドバイスありがとうございます。
Dentalさんのおっしゃるようにもうちょっと詳しく書くべきですね。
すみません。

データはテキスト(TSV)から読み込みます。

12345678901111  あああ
11111111111111  えええ
12345678902222  いいい
11111111112222  おおお
12345678903333  ううう
11111111113333  かかか

こういう形で、さっき正確に件数を見たら100万件程ありました。
これを、ハッシュテーブルなどに読み込み、
たとえばキーの先頭10バイトが"1234567890"のデータをすべて
抽出する、と言う風な処理を行いたいのです。
ハッシュテーブルだと、TSVファイルから全件格納するのは3分くらい
で終わるのですが、キーの先頭10バイトに該当するデータを
抽出する処理に時間がかかってしまいます。
この処理が、スムーズに言ってくれることが一番の理想なんですが・・・。

また先程から、教えていただいたSortedListに格納しようとしてるのですが、
2時間たった今でもまだ処理が終わっていません・・・・。

どうにかスムーズに行う方法はありませんでしょうか?


ねろ  2005-08-25 22:03:07  No: 124392

100万件ですか、通常はデーターベースで処理でしょうが、
DosコマンドのFindで検索してリダイレクトでファイルに吐き出す手も有る。
データーがあまり変わらなければ、DosコマンドでSortして配列に入れ、
配列上で検索する手も有る。


ねろ  2005-08-25 22:57:00  No: 124393

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() '終了
これで遅かったらごめんなさい。


魔界の仮面弁士  2005-08-25 23:14:03  No: 124394

同時に、何か別の処理を行っていませんか?(画面更新とか)
もしくは、データに極端な偏りがあるとか。

実際に、200万レコードのTSVファイルを作って、先の回答にあった
「階層化されたHashtable」の手法で試してみましたが、
そんなに時間は掛からなかったのですが……。

PCスペックとデータのばらつき度合いにもよりますが、当方では、
『キーの先頭10バイトが"1234567890"のデータの列挙』は、
0.02秒〜0.8秒といったところでしたし、200万件のデータを
階層ハッシュ化するのも、12秒〜40秒程度で完了しました。


ねろ  2005-08-26 00:15:43  No: 124395

私の書いた、SotedListも1,000,000件ののデーターセットに
約15秒、検索は0.5秒以下ですが。
もしかしてデバッグの為に付けた、ListBoxにデーターを
表示させてません?
ListBox1.Items.Add(MySotedList.GetKey(i))
これはやってはいけませんよ。


※返信する前に利用規約をご確認ください。




  


  このエントリーをはてなブックマークに追加