相同算法的两个实现之间的性能差异

我正在研究一个将需要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

相同算法的两个实现之间的性能差异

回答

相关问题