0

私は、2 つの文字列の類似性を計算するためにレーベンシュタイン アルゴリズムを必要とするアプリケーションに取り組んでいます。

少し前に、C# バージョン (インターネットで簡単に見つけられる) を VB.NET に適合させたところ、次のようになりました。

Public Function Levenshtein1(s1 As String, s2 As String) As Double
    Dim n As Integer = s1.Length
    Dim m As Integer = s2.Length

    Dim d(n, m) As Integer
    Dim cost As Integer
    Dim s1c As Char

    For i = 1 To n
        d(i, 0) = i
    Next
    For j = 1 To m
        d(0, j) = j
    Next

    For i = 1 To n
        s1c = s1(i - 1)

        For j = 1 To m
            If s1c = s2(j - 1) Then
                cost = 0
            Else
                cost = 1
            End If

            d(i, j) = Math.Min(Math.Min(d(i - 1, j) + 1, d(i, j - 1) + 1), d(i - 1, j - 1) + cost)
        Next
    Next

    Return (1.0 - (d(n, m) / Math.Max(n, m))) * 100
End Function

次に、微調整してパフォーマンスを向上させようとして、バージョンで終了しました。

Public Function Levenshtein2(s1 As String, s2 As String) As Double
    Dim n As Integer = s1.Length
    Dim m As Integer = s2.Length

    Dim d(n, m) As Integer
    Dim s1c As Char
    Dim cost As Integer

    For i = 1 To n
        d(i, 0) = i
        s1c = s1(i - 1)

        For j = 1 To m
            d(0, j) = j

            If s1c = s2(j - 1) Then
                cost = 0
            Else
                cost = 1
            End If

            d(i, j) = Math.Min(Math.Min(d(i - 1, j) + 1, d(i, j - 1) + 1), d(i - 1, j - 1) + cost)
        Next
    Next

    Return (1.0 - (d(n, m) / Math.Max(n, m))) * 100
End Function

基本的に、距離の配列 d(,) は、2 つの初期 (および追加) サイクルを必要とする代わりに、サイクルのメイン内で初期化できると考えました。これは大きな改善になると本当に思っていました...残念ながら、オリジナルよりも改善されていないだけでなく、実際には動作が遅くなります!

生成された IL コードを見て両方のバージョンを分析しようとしましたが、理解できません。

だから、誰かがこの問題に光を当て、2 番目のバージョン (サイクル数が少ない場合でも) が元のバージョンよりも遅い理由を説明できることを望んでいましたか?

注: 時間差は約 0.15 ナノ秒です。これは大したことではないように見えますが、何千万もの文字列をチェックする必要がある場合、その違いは非常に顕著になります。

4

3 に答える 3

2

これは次の理由によるものです。

 For i = 1 To n
        d(i, 0) = i
        s1c = s1(i - 1)

        For j = 1 To m
            d(0, j) = j 'THIS LINE HERE

最初はこの配列を初期化していましたが、現在はn回初期化しています。このような配列内のメモリへのアクセスにはコストがかかりますが、これをn回余分に行っています。次のように行を変更できますIf i = 1 Then d(0, j) = j。ただし、私のテストでは、基本的には元のバージョンよりもわずかに遅いバージョンになります。そして、それはまた理にかなっています。この if ステートメントを n*m 回実行しています。やはり費用はかかります。元のバージョンのように移動すると、はるかに安くなります。最終的には O(n) になります。全体的なアルゴリズムは O(n*m) であるため、O(n) ステップに移動できるステップはすべて勝利になります。

于 2012-09-12T23:24:34.683 に答える
2

次の行を分割できます。

d(i, j) = Math.Min(Math.Min(d(i - 1, j) + 1, d(i, j - 1) + 1), d(i - 1, j - 1) + cost)

次のように：

tmp = Math.Min(d(i - 1, j), d(i, j - 1)) + 1
d(i, j) = Math.Min(tmp, d(i - 1, j - 1) + cost)

このようにして、1回の合計を回避します

さらに、最後の "min" 比較を if 部分内に配置して、コストの割り当てを回避できます。

tmp = Math.Min(d(i - 1, j), d(i, j - 1)) + 1
If s1c = s2(j - 1) Then
   d(i, j) = Math.Min(tmp, d(i - 1, j - 1))
Else
   d(i, j) = Math.Min(tmp, d(i - 1, j - 1)+1)
End If

したがって、s1c = s2(j - 1) の場合に合計を保存します。

于 2013-02-13T17:12:31.570 に答える
0

あなたの質問に対する直接的な答えではありませんが、パフォーマンスを高速化するには、多次元配列の代わりにジャグ配列 (配列の配列) を使用することを検討する必要があります。C#の多次元配列と配列の配列の違いは何ですか? および.NET の多次元配列が通常の配列よりも遅いのはなぜですか?

多次元配列のコード サイズが 10 であるのに対し、ジャグ配列のコード サイズは 7 であることがわかります。

以下のコードは、ジャグ配列、1 次元配列を使用しています

Public Function Levenshtein3(s1 As String, s2 As String) As Double
    Dim n As Integer = s1.Length
    Dim m As Integer = s2.Length

    Dim d()() As Integer = New Integer(n)() {}
    Dim cost As Integer
    Dim s1c As Char

    For i = 0 To n
        d(i) = New Integer(m) {}
    Next

    For j = 1 To m
        d(0)(j) = j
    Next

    For i = 1 To n
        d(i)(0) = i
        s1c = s1(i - 1)

        For j = 1 To m
            If s1c = s2(j - 1) Then
                cost = 0
            Else
                cost = 1
            End If

            d(i)(j) = Math.Min(Math.Min(d(i - 1)(j) + 1, d(i)(j - 1) + 1), d(i - 1)(j - 1) + cost)
        Next
    Next

    Return (1.0 - (d(n)(m) / Math.Max(n, m))) * 100
End Function
于 2012-09-13T11:28:13.977 に答える