为什么Python内置str.replace比自行实现的KMP字符串替换算法快得多？

性能差距核心原因 #

1. 执行层本质差异：你实现的版本是纯Python代码，所有循环、判断、字符串操作都在Python解释器层执行字节码，有大量对象操作的额外开销。而内置的str.replace是CPython底层用C语言实现的，直接操作内存，无Python层的额外开销，本身执行效率就有几十到上百倍的差距。
2. 你的实现存在性能缺陷，未达到理论O(N)复杂度：Python的字符串是不可变对象，你每次匹配到模式就执行s = s[:i - 2 * len(p) + shift] + c + s[i - len(p) + shift:]，这个操作每次都会生成全新的字符串，需要拷贝原有字符串的全部内容。你用的测试用例是1e5个a替换为ab，会触发1e5次字符串拼接，实际时间复杂度直接退化为O(N²)，这是性能差的最主要原因。
3. 内置实现的优化更充分：CPython的str.replace会先扫描一遍字符串统计匹配总次数，预先计算出最终字符串的总长度，一次性分配好内存，再依次把原内容和替换内容拷贝进去，全程只有一次内存分配和两次全量拷贝，完全没有重复拷贝的开销。

CPython的str.replace底层算法 #

• 对于单字符、短模式的场景，会使用高度优化的朴素匹配算法，没有预处理开销，缓存命中率高，实际运行效率比KMP更高。
• 对于长模式的场景，使用的是Two-Way字符串匹配算法，属于线性时间复杂度算法，预处理开销比KMP更低，加上C语言层面的极致优化，效率远高于Python实现的同复杂度算法。

如果要优化你自己的KMP实现，可以先遍历一遍记录所有匹配的位置，最后根据匹配位置一次性拼接生成结果字符串，就能达到理论O(N)复杂度，性能会比你当前的版本提升很多。

内容的提问来源于stack exchange，提问作者FTSlow