字符串匹配性能：gcc与CPython

字符串匹配性能：gcc与CPython

python 3.4代码

b'abc' inb'abcabc'

（或

b'abcabc'.__contains__(b'abc')

如您的示例所示）执行

bytes_contains

方法，该方法又调用内联函数

stringlib_find

；将搜索委派给

FASTSEARCH

。

FASTSEARCH

然后，该函数使用简化的Boyer-
Moore
搜索算法（Boyer-
Moore-
Horspool
）：

快速的搜索/计数实现，基于博耶摩尔和霍尔斯普尔的混合体，顶部还有更多的花哨功能。有关更多背景信息，请参见：http

//effbot.org/zone/stringlib.htm

如评论所述，也有一些修改：

注意：fastsearch可以访问

s[n]

，这在使用Python的普通字符串类型时不是问题，但是如果在其他上下文中使用此代码，则可能会导致问题。同样，

-1

如果目标字符串中不可能存在匹配项，并且

0

实际上已经检查了匹配项但没有找到匹配项，则计数模式将返回。来电者要当心！

---

的GNU C
++标准库

basic_string<T>::find()

实现是通用的（和哑）成为可能;
它只是在每个连续的字符位置尝试哑匹配模式，直到找到匹配为止。

---

TL; DR ：C
++标准库之所以与Python相比如此之慢，是因为它试图在之上执行通用算法

std::basic_string<char>

，但在更有趣的情况下却无法有效地实现；而在Python中，程序员可以根据情况免费获得最高效的算法。