相同算法的兩個實現之間的性能差異

我正在研究一個將需要Levenshtein算法來計算兩個字符串的相似度的應用程序。相同算法的兩個實現之間的性能差異

隨着前段時間我適應一個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

然後，試圖調整，並改善其性能，I與版本結束：

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（）的陣列可以在主要爲週期內進行初始化。我真的認爲這將是一個巨大的進步......不幸的是，它不僅沒有改善原來的效果，反而變慢了！

我已經試着通過查看生成的IL代碼來分析兩個版本，但我無法理解它。

所以，我希望有人能夠解釋這個問題，並解釋爲什麼第二個版本（即使它的週期較少）運行速度比原來慢？

注：時間差約爲0.15納秒。這看起來並不多，但是當你必須檢查數千萬個字符串時......差異變得相當顯着。

來源

2012-09-12 xfx

這是因爲這一點：

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次。您可以更改該行以說：If i = 1 Then d(0, j) = j。但是，在我的測試中，你基本上最終會得到比原來稍慢的版本。這又是有道理的。你正在執行這個if語句n * m次。再次有一些成本。將它移出原來的版本便宜很多它最終成爲O（n）。由於整體算法是O（n * m），任何可以移出O（n）步的步驟都將成爲贏家。

來源

2012-09-12 23:24:34 aquinas

我怎麼錯過那！？非常感謝！ – xfx

我剛剛將循環內部的行的初始化移動了一遍，現在第二個版本的算法比原始版本快了40％ - 所以再次感謝您！（我生我的氣，因爲沒有看到！） – xfx

不是您的問題的直接答案，但爲了提高性能，您應該考慮使用鋸齒陣列（數組數組）而不是多維數組。 What are the differences between a multidimensional array and an array of arrays in C#?和

您將看到鋸齒陣列的代碼大小爲7而不是多維數組的10。

下面的代碼是使用交錯數組，一維陣列

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-13 11:28:13 Seph

謝謝你的建議Seph。我會試一試，但恐怕for循環初始化數組的第二維將會消除鋸齒陣列可以提供的任何改進。 – xfx

這絕對是一個改進。比算法的第2版少約10-15毫秒。 – xfx

您可以分割下面的行：如下

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)

它這樣你避免一個總和

進一步您可以將最後的「分鐘」內，如果部分比較，避免分配成本：

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-13 17:12:31 goicox

相同算法的兩個實現之間的性能差異

回答

相關問題