c# - 我执行的 KMP 算法有什么问题？

Question

static void Main(string[] args)
{
    string str = "ABC ABCDAB ABCDABCDABDE";//We should add some text here for 
                                           //the performance tests.

    string pattern = "ABCDABD";


    List<int> shifts = new List<int>();

    Stopwatch stopWatch = new Stopwatch();

    stopWatch.Start();
    NaiveStringMatcher(shifts, str, pattern);
    stopWatch.Stop();
    Trace.WriteLine(String.Format("Naive string matcher {0}", stopWatch.Elapsed));

    foreach (int s in shifts)
    {
        Trace.WriteLine(s);
    }

    shifts.Clear();
    stopWatch.Restart();

    int[] pi = new int[pattern.Length];
    Knuth_Morris_Pratt(shifts, str, pattern, pi);
    stopWatch.Stop();
    Trace.WriteLine(String.Format("Knuth_Morris_Pratt {0}", stopWatch.Elapsed));

    foreach (int s in shifts)
    {
        Trace.WriteLine(s);
    }

    Console.ReadKey();
}

static IList<int> NaiveStringMatcher(List<int> shifts, string text, string pattern)
{
    int lengthText = text.Length;
    int lengthPattern = pattern.Length;

    for (int s = 0; s < lengthText - lengthPattern + 1; s++ )
    {
        if (text[s] == pattern[0])
        {
            int i = 0;
            while (i < lengthPattern)
            {
                if (text[s + i] == pattern[i])
                    i++;
                else break;
            }
            if (i == lengthPattern)
            {
                shifts.Add(s);                        
            }
        }
    }

    return shifts;
}

static IList<int> Knuth_Morris_Pratt(List<int> shifts, string text, string pattern, int[] pi)
{

    int patternLength = pattern.Length;
    int textLength = text.Length;            
    //ComputePrefixFunction(pattern, pi);

    int j;

    for (int i = 1; i < pi.Length; i++)
    {
        j = 0;
        while ((i < pi.Length) && (pattern[i] == pattern[j]))
        {
            j++;
            pi[i++] = j;
        }
    }

    int matchedSymNum = 0;

    for (int i = 0; i < textLength; i++)
    {
        while (matchedSymNum > 0 && pattern[matchedSymNum] != text[i])
            matchedSymNum = pi[matchedSymNum - 1];

        if (pattern[matchedSymNum] == text[i])
            matchedSymNum++;

        if (matchedSymNum == patternLength)
        {
            shifts.Add(i - patternLength + 1);
            matchedSymNum = pi[matchedSymNum - 1];
        }

    }

    return shifts;
}

为什么我实现的 KMP 算法比朴素字符串匹配算法运行速度慢？

Answer 1

KMP 算法有两个阶段:首先建立一个表，然后根据表的内容进行搜索。

朴素算法有一个阶段:它进行搜索。与 KMP 搜索阶段相比，它在最坏情况下的搜索效率要低得多。

如果 KMP 比朴素算法慢，那可能是因为构建表格花费的时间比一开始简单地简单地搜索字符串所花的时间要长。朴素的字符串匹配在短字符串上通常非常很快。我们不在字符串搜索的 BCL 实现中使用像 KMP 这样花哨的算法是有原因的。在您设置表格时，您可能已经使用朴素算法完成了六次短字符串搜索。

KMP 只有在您拥有大量 字符串并且您正在执行大量 允许您重新使用已建表的搜索时才是胜利。您需要通过使用该表进行大量搜索来分摊构建该表的巨大成本。

此外，朴素算法仅在奇怪且不太可能的情况下表现不佳。大多数人都在像“Buckingham Palace, London, England”这样的字符串中搜索像“London”这样的词，而不是在像“BANAN BANBAAN BANBANANA BANAN BANAN BANANAN BANANANANANANANANA...”这样的字符串中搜索像“BANANANANANANANA”这样的字符串。朴素搜索算法对第一个问题是最优的，对后一个问题是次优的；但针对前者而不是后者进行优化是有意义的。

换一种说法:如果搜索字符串长度为w，搜索字符串长度为n，则KMP为O(n) + O(w)。朴素算法是最坏情况 O(nw)，最好情况 O(n + w)。但这并没有说明“常数因子”! KMP 算法的常数因子比朴素算法的常数因子大得多。 n 的值必须非常大，次优部分匹配的数量必须非常大，KMP 算法才能战胜速度极快的朴素算法。

处理算法复杂性问题。您的方法也不是很好，这可以解释您的结果。请记住，第一次您运行代码时，抖动必须将 IL 转换为汇编代码。 在某些情况下，这可能比运行该方法花费的时间更长。你真的应该在一个循环中运行代码几十万次，丢弃第一个结果，并对其余的时间取平均值。

如果你真的想知道发生了什么，你应该使用分析器来确定热点是什么。同样，如果您希望得到的结果不受 jit 时间的影响，请确保您测量的是 post-jit 运行，而不是代码被 jit 的运行。