str.find 怎么这么快？

我之前遇到过一个问题，我在迭代字符串并使用切片时寻找子字符串。原来这是一个really关于性能的坏主意。str.find速度要快得多。但我不明白为什么？

import random
import string
import timeit

# Generate 1 MB of random string data
haystack = "".join(random.choices(string.ascii_lowercase, k=1_000_000))

def f():
    return [i for i in range(len(haystack)) if haystack[i : i + len(needle)] == needle]

def g():
    return [i for i in range(len(haystack)) if haystack.startswith(needle, i)]

def h():
    def find(start=0):
        while True:
            position = haystack.find(needle, start)
            if position < 0:
                return
            start = position + 1
            yield position
    return list(find())

number = 100
needle = "abcd"
expectation = f()
for func in "fgh":
    assert eval(func + "()") == expectation
    t = timeit.timeit(func + "()", globals=globals(), number=number)
    print(func, t)

Results:

f 26.46937609199813
g 16.11952730899793
h 0.07721933699940564

f and g很慢，因为他们检查是否needle可以在每个可能的位置找到haystack导致O(n m)复杂。f由于创建新字符串对象的切片操作（正如 Barmar 在评论中指出的那样），速度较慢。

h速度很快，因为它可以跳过许多位置。例如，如果needle未找到字符串，只有一个find被执行。内置的find函数在 C 语言中进行了高度优化，因此比解释的纯 Python 代码更快。此外，find函数使用称为的有效算法克罗什莫尔和佩兰的双向 https://en.wikipedia.org/wiki/Two-way_string-matching_algorithm。该算法比搜索快得多needle在每一个可能的位置haystack当字符串比较大时。相关的CPython代码可用here https://github.com/python/cpython/blob/f4c03484da59049eb62a9bf7777b963e2267d187/Objects/stringlib/fastsearch.h.

如果出现的次数相对较少，那么您的实施应该已经很好了。否则，最好使用基于 CPTW 算法的自定义变体KMP算法 https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm但在纯 Python 中这样做效率非常低。您可以使用 C 或 Cython 来完成此操作。话虽这么说，这并不是一件微不足道的事情，也不是很好维护。