10
\$\begingroup\$

After reading this answer to the question "High execution time to count overlapping substrings", I decided to implement the suggested Knuth-Morris-Pratt (KMP) algorithm. I used the pseudo-code listed on Wikipedia for the functions kmp_table and kmp_search.

However, when running it on some corner-cases, I have observed that it is a lot slower than the standard str.find, which apparently uses a modified Boyer-Moore-Horspool algorithm and should thus have worse worst-case performance.

The specific case I looked at is:

$ ipython -i kmp.py
In [1]: text = "A"*1000000 + "B"
In [2]: word = "A"*100 + "B"
In [3]: %timeit kmp_search(text, word)
1 loop, best of 3: 410 ms per loop
In [4}: %timeit text.find(word)
1000 loops, best of 3: 703 µs per loop

So the difference is about a factor 1000 for this input. This is probably due to the fact that the native one is written in C and this is written in Python, but I still wanted to see if I did anything stupid here or missed any obvious optimization.

def kmp_table(word):
    table = [0] * len(word)
    position, candidate = 2, 0
    table[0] = -1

    while position < len(word):
        if word[position - 1] == word[candidate]:
            table[position] = candidate + 1
            candidate += 1
            position += 1
        elif candidate > 0:
            candidate = table[candidate]
        else:
            table[position] = 0
            position += 1
    return table


def kmp_search(text, word):
    m, i = 0, 0
    table = kmp_table(word)
    while m + i < len(text):
        if word[i] == text[m + i]:
            if i == len(word) - 1:
                return m
            i += 1
        else:
            if table[i] > -1:
                m += i - table[i]
                i = table[i]
            else:
                m += 1
                i = 0
    return len(text)
\$\endgroup\$
  • \$\begingroup\$ I'm not quite willing to put ~600:1 to CPython vs. native. Just wondering if explicitly moving len(text)/word changes anything. The specific case seems to be worst case for KMP and best case for BM(H). \$\endgroup\$ – greybeard Apr 19 '17 at 21:02
  • \$\begingroup\$ I guess table = [0] * len(word) should be table = [0] * (len(word)+1). \$\endgroup\$ – pgs Apr 20 '17 at 18:22
  • \$\begingroup\$ @pgs why? position is always less than len(word). \$\endgroup\$ – Graipher Apr 20 '17 at 18:29
  • 1
    \$\begingroup\$ @greybeard That sounds like the start of a good answer ;-) \$\endgroup\$ – Graipher Apr 20 '17 at 18:30
3
+50
\$\begingroup\$

One immediate, fairly significant improvement that I see would be to calculate len(text) and len(word) - 1 outside of the loop in kmp_search. This provided a 30%-50% reduction in time in my tests depending on the computer and Python version.

def kmp_search(text, word):
    m, i = 0, 0
    table = kmp_table(word)
    LT = len(text)
    LW = len(word) - 1
    while m + i < LT:
        if word[i] == text[m + i]:
            if i == LW:
                return m
            i += 1
        else:
            if table[i] > -1:
                m += i - table[i]
                i = table[i]
            else:
                m += 1
                i = 0
    return LT
\$\endgroup\$
  • \$\begingroup\$ but what about stackoverflow.com/questions/37848483/… which says it's O(1)? LW might be a speed-up, though. \$\endgroup\$ – Pimgd Apr 22 '17 at 10:44
  • 2
    \$\begingroup\$ @Pimgd I believe it's the function call that's the issue, not the complexity of len \$\endgroup\$ – Jared Goguen Apr 22 '17 at 12:37
  • \$\begingroup\$ Yeah, I guess caching the len does seem to reduce the runtime somewhat (even though it is not even close to the str.find time). I chose your answer, because it is a nice optimization to keep in mind, even though pimgd's answer gives a comparable speed-boost. \$\endgroup\$ – Graipher Apr 25 '17 at 13:23
3
\$\begingroup\$

Minor comments, but...

    else:
        if table[i] > -1:
            m += i - table[i]
            i = table[i]
        else:
            m += 1
            i = 0

This sort of construct, an else which contains only an if-else chain, can be simply written as an elif-else chain.

    elif table[i] > -1:
        m += i - table[i]
        i = table[i]
    else:
        m += 1
        i = 0

        table[position] = candidate + 1
        candidate += 1

These statements seem weird, why not first add one and then set?

        candidate += 1
        table[position] = candidate
\$\endgroup\$
  • 1
    \$\begingroup\$ Your comments are valid and improve the readability and even speed things up slightly (who would've thought the simple fact that I'm calculating candidate + 1 twice would make a difference). Nevertheless I chose Jared's answer because it is more of an optimization and he needs the points more than you :) \$\endgroup\$ – Graipher Apr 25 '17 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.