タグ:

文字列の検索方法

文字列を検索するときにとりあえず考えれれる方法は

  1. Stringにどんどん追加し、単語単位で区切り文字を入れていく。そのStringのContainsメゾットを使用して検査する

  2. Stringにどんどん追加し、単語単位で区切り文字を入れていく。そのStringから正規表現のオブジェクトを作成し、正規表現にて一致するかで検査する。

  3. 単語単位で配列に格納し、その配列から線形検索することで検査する。

  4. 単語単位でHashTableのキーを作成し、キーの有無によって検査する。


検証

検証に用いるアルゴリズムは、アルファベットのみで構成されたランダムな文字列を作成し配列に格納する。

その配列を先頭から検査し、今まで検査した単語ではないかを確認する。

コード(VB.net)

Imports System.Text
Imports System.Text.RegularExpressions

Module Module1
    Private Const testCount As Integer = 100000
    Private randTxt As New ArrayList(testCount)

    Sub Main()

        Do While randTxt.Count < testCount
            Dim pass As String = System.Web.Security.Membership.GeneratePassword(2, 0)
            pass = Regex.Replace(pass, "[^A-Za-z]", "")
            If Not pass = String.Empty Then
                randTxt.Add(pass)
            End If
        Loop

        TestInStr()
        TestRegex()
        TestArray()
        TestHash()
        TestDic()
        Console.ReadKey()
    End Sub

    Private Sub TestInStr()
        Const MethodName As String = "TestInStr"
        Dim ptr As String = ""
        Dim hitCount As Integer = 0
        Dim sw As New System.Diagnostics.Stopwatch()
        sw.Start()
        For Each p As String In randTxt
            Dim ret As Boolean = ptr.Contains("|" & p & "|")
            If Not ret Then
                ptr &= "|" & p & "|"
            Else
                hitCount += 1
            End If
        Next
        sw.Stop()
        Console.WriteLine(MethodName & vbTab & sw.Elapsed.ToString() & vbTab & hitCount)
    End Sub

    Private Sub TestRegex()
        Const MethodName As String = "TestRegex"
        Dim ptr As String = ""
        'Dim regObj As New Regex("([\\\.\+\*\[\]\(\)])")
        Dim sw As New System.Diagnostics.Stopwatch()
        Dim hitCount As Integer = 0
        sw.Start()
        For Each p As String In randTxt
            Dim ret As Boolean = False
            If ptr.Length > 0 Then
                ret = Regex.IsMatch(p, "^(" & ptr & ")$")
            End If
            If Not ret Then
                If ptr.Length = 0 Then
                    ptr = p
                Else
                    ptr &= "|" & p
                End If
            Else
                hitCount += 1
            End If
        Next
        sw.Stop()
        Console.WriteLine(MethodName & vbTab & sw.Elapsed.ToString() & vbTab & hitCount)
    End Sub

    Private Sub TestArray()
        Const MethodName As String = "TestArray"
        Dim ptr As New ArrayList()
        Dim hitCount As Integer = 0
        Dim sw As New System.Diagnostics.Stopwatch()
        sw.Start()
        For Each p As String In randTxt
            Dim ret As Boolean = False
            For Each i As String In ptr
                If i = p Then
                    ret = True
                    Exit For
                End If
            Next
            If Not ret Then
                ptr.Add(p)
            Else
                hitCount += 1
            End If
        Next
        sw.Stop()
        Console.WriteLine(MethodName & vbTab & sw.Elapsed.ToString() & vbTab & hitCount)
    End Sub

    Private Sub TestHash()
        Const MethodName As String = "TestHash"
        Dim ptr As New Hashtable()
        Dim sw As New System.Diagnostics.Stopwatch()
        Dim hitCount As Integer = 0
        sw.Start()
        For Each p As String In randTxt
            Dim ret As Boolean = ptr.ContainsKey(p)
            If ret Then
                hitCount += 1
            Else
                ptr.Add(p, "")
            End If
        Next
        sw.Stop()
        Console.WriteLine(MethodName & vbTab & sw.Elapsed.ToString() & vbTab & hitCount)

    End Sub

    Private Sub TestDic()
        Const MethodName As String = "TestDic "
        Dim ptr As New Dictionary(Of String, String)
        Dim sw As New System.Diagnostics.Stopwatch()
        Dim hitCount As Integer = 0
        sw.Start()
        For Each p As String In randTxt
            Dim ret As Boolean = ptr.ContainsKey(p)
            If ret Then
                hitCount += 1
            Else
                ptr.Add(p, "")
            End If
        Next
        sw.Stop()
        Console.WriteLine(MethodName & vbTab & sw.Elapsed.ToString() & vbTab & hitCount)

    End Sub

End Module

一致した数をカウントしているのは検算用です。これがすべてのメゾットで一致していることが検出条件の一致と前提しています。


結果

方法

サンプル内メゾット名

経過時間(1万件)

方法

StringのContainsメゾットを使用

サンプル内メゾット名

TestInStr

経過時間(1万件)

1.27秒

方法

正規表現を使用

サンプル内メゾット名

testRegex

経過時間(1万件)

14.38秒

方法

配列からの検索

サンプル内メゾット名

testArray

経過時間(1万件)

2.62秒

方法

HashTableでの検索

サンプル内メゾット名

TestHash

TestArray

経過時間(1万件)

0.01秒

TestArrayはDictionaryを使用した場合です。HashTableとは特に変化はありませんでした。