我有一个较早的问题，我正在寻找一个子字符串，而迭代字符串和使用切片。事实证明，对于性能而言，这是一个真的坏主意。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)
结果:
f 26.46937609199813
g 16.11952730899793
h 0.07721933699940564
f和g是缓慢的，因为它们检查needle是否可以在haystack的每个可能位置找到，从而导致O(n m)的复杂性。f比较慢，因为切片操作会创建一个新的字符串对象(正如Barmar在评论中指出的那样)。
h是快速的，因为它可以跳过许多位置。例如，如果没有找到needle字符串，则只执行一个find。内置的find函数在C中进行了高度优化，因此比解释的纯python代码更快。此外，find函数使用一种称为Crochemore和Perrin双向的高效算法。当字符串比较大时，该算法比在haystack的每个可能位置搜索needle要快得多。相关的CPython代码可以在这里找到。
如果出现的次数相对较少，那么您的实现应该已经很好了。否则，使用基于CPTW算法(可能是KMP算法)的自定义变体可能会更好，但在纯python中这样做将非常低效。你可以用C或Cython来做。也就是说，这不是一件微不足道的事情，也不是很好维护。
内置的Python函数是用C实现的，这使得它们更快。当使用Python时，不可能使一个函数执行得同样好。