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

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

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

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

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

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

Answer 2

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

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

Answer 3

Простая реализация поиска KMPSubstring.

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 
*/