Блог

 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) amp;amp; (pattern[i] == pattern[j]))
        {
            j  ;
            pi[i  ] = j;
        }
    }

    int matchedSymNum = 0;

    for (int i = 0; i < textLength; i  )
    {
        while (matchedSymNum > 0 amp;amp; 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 работает медленнее, чем алгоритм наивного сопоставления строк?

Алгоритм KMP состоит из двух фаз: сначала он создает таблицу, а затем выполняет поиск, ориентированный на содержимое таблицы.

Наивный алгоритм имеет одну фазу: он выполняет поиск. Этот поиск выполняется гораздо менее эффективно, в худшем случае, чем этап поиска KMP.

Если KMP работает медленнее, чем наивный алгоритм, то это вероятно потому, что построение таблицы занимает у вас больше времени, чем требуется для простого наивного поиска строки в первую очередь. Наивное сопоставление строк обычно выполняется очень быстро для коротких строк. Есть причина, по которой мы не используем навороченные алгоритмы, такие как KMP, в реализациях поиска строк на BCL. К тому времени, когда вы настроили таблицу, вы могли бы выполнить полдюжины поисков коротких строк с помощью наивного алгоритма.

KMP выигрывает только в том случае, если у вас есть огромные строки и вы выполняете много поисковых запросов, которые позволяют повторно использовать уже созданную таблицу. Вам нужно амортизировать огромные затраты на построение таблицы, выполняя множество поисковых запросов с использованием этой таблицы.

Кроме того, наивный алгоритм имеет плохую производительность только в причудливых и маловероятных сценариях. Большинство людей ищут слова, как «Лондон» в строках, как «Букингемский дворец, Лондон, Англия», а не поиск строки вроде «BANANANANANANA» в строках типа «банан проживанием в семье banban BANBANANA банан Банан Бананан BANANANANANANANANAN…». Наивный алгоритм поиска оптимального для первой задаче весьма неоптимальным для последней проблемы, но это имеет смысл для оптимизации прежний, не последний.

Другой способ выразить это: если искомая строка имеет длину w, а искомая строка имеет длину n, то KMP равен O (n) O (w). Наивный алгоритм — это наихудший вариант O (nw), наилучший вариант O (n w). Но это ничего не говорит о «постоянном факторе»! Постоянный коэффициент алгоритма KMP намного больше, чем постоянный коэффициент наивного алгоритма. Значение n должно быть ужасно большим, а количество неоптимальных частичных совпадений должно быть ужасно большим, чтобы алгоритм KMP одержал победу над невероятно быстрым наивным алгоритмом.

Это касается проблем алгоритмической сложности. Ваша методология также не очень хороша, и это может объяснить ваши результаты. Помните, что при первом запуске кода джиттер должен вставлять IL в ассемблерный код. В некоторых случаях это может занять больше времени, чем запуск метода. Вы действительно должны запускать код несколько сотен тысяч раз в цикле, отбрасывая первый результат и принимая среднее значение таймингов остальных.

Если вы действительно хотите знать, что происходит, вам следует использовать профилировщик, чтобы определить, что такое горячая точка. Опять же, убедитесь, что вы измеряете выполнение после jit, а не выполнение, в котором код jitted, если вы хотите получить результаты, которые не искажены временем jit.

Ваш пример слишком мал, и в нем недостаточно повторений шаблона, в котором KMP избегает обратного отслеживания.

В некоторых случаях KMP может быть медленнее обычного поиска.

Простая реализация KMPSubstringSearch.

https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/KMPSubstringSearch.cs

 using System;
using System.Collections.Generic;
using System.Linq;

namespace AlgorithmsMadeEasy
{
    class KMPSubstringSearch
    {
        public void KMPSubstringSearchMethod()
        {
            string text = System.Console.ReadLine();
            char[] sText = text.ToCharArray();

            string pattern = System.Console.ReadLine();
            char[] sPattern = pattern.ToCharArray();

            int forwardPointer = 1;
            int backwardPointer = 0;

            int[] tempStorage = new int[sPattern.Length];
            tempStorage[0] = 0;

            while (forwardPointer < sPattern.Length)
            {
                if (sPattern[forwardPointer].Equals(sPattern[backwardPointer]))
                {
                    tempStorage[forwardPointer] = backwardPointer   1;
                    forwardPointer  ;
                    backwardPointer  ;
                }
                else
                {
                    if (backwardPointer == 0)
                    {
                        tempStorage[forwardPointer] = 0;
                        forwardPointer  ;
                    }
                    else
                    {
                        int temp = tempStorage[backwardPointer];
                        backwardPointer = temp;
                    }

                }
            }

            int pointer = 0;
            int successPoints = sPattern.Length;
            bool success = false;
            for (int i = 0; i < sText.Length; i  )
            {
                if (sText[i].Equals(sPattern[pointer]))
                {
                    pointer  ;
                }
                else
                {
                    if (pointer != 0)
                    {
                        int tempPointer = pointer - 1;
                        pointer = tempStorage[tempPointer];
                        i--;
                    }
                }

                if (successPoints == pointer)
                {
                    success = true;
                }
            }

            if (success)
            {
                System.Console.WriteLine("TRUE");
            }
            else
            {
                System.Console.WriteLine("FALSE");
            }
            System.Console.Read();
        }
    }
}

/*
 * Sample Input
abxabcabcaby
abcaby 
*/