brute force VS. KMP algorithm

brute force vs. KMP 알고리즘의 속도를 비교해봤다.

제한 조건은 다음과 같다.

• https://en.wikipedia.org/wiki/algorithm 문서 100개 분량(복사 붙여넣기 X100)
• 검색 문자열 "algorithm"

 

위 제한 조건으로 C#에서 탐색한 결과 대략적으로 아래의 결과를 보였다.

bruteforce - 100ms

KMP algorithm - 50ms

 

1회 실행의 실행시간 비가 bruteforce:KMP algorithm = 2:1이 나온다

// bruteforce
List<int> list = new List<int>();
string str = richTextBox1.Text;
string pattern = textBox1.Text;

for(int i = 0; i< str.Length - pattern.Length; ++i)
{
    var substr = str.Substring(i, pattern.Length);
    if(substr == pattern)
    {
        list.Add(i);
    }
}

 

// KMP algorithm
private void FailureFunction(List<int> a, string p)
{
    int i = 1; int j = 0;
    while (i < p.Length)
    {
        if (p[i] == p[j])
        {
            a[i] = j + 1;
            i++; j++;
        }
        else if (j > 0)
        {
            j = a[j - 1];
        }
        else
        {
            // a[i] = 0; // already initialize by zero
            i++;
        }
    }
}

private List<int> KMPSearch(string t, string p)
{
    List<int> ans = new List<int>();
    List<int> f = new List<int>();
    {
        for (int i = 0; i < p.Length; ++i) f.Add(0);
    }

    if (p.Length == 0) return new List<int>();

    FailureFunction(f, p);
    {

        int i, j;
        i = j = 0;
        while (i < t.Length)
        {
            if (t[i] == p[j])
            {
                j++;
                if (j == p.Length)
                {
                    j = 0;
                    ans.Add(i - j -1);
                }
                i++;
            }
            else if (j > 0)
            {
                j = f[j - 1];
            }
            else
            {
                i++;
            }
        }
    }

    return ans;
}

 

---

 

이와 별개로, 기본제공함수인 string.IndexOf를 이용해 찾아가는 경우 bruteforce 방식보다 수 십 배 느린 결과를 가져왔다.

예측으로는 IndexOf를 호출할 때 발생하는 오버헤드로 인해 발생하는 문제로 보인다.

while (true)
{
    int val = str.IndexOf(textBox1.Text, start);
    if (val == -1 || val > str.Length) break;
    list.Add(val);
    start = val+1;
}