为什么 str.replace 这么快？

Question

我目前正在学习和练习字符串算法。具体来说，我正在尝试用一些修改替换基于 KMP 的字符串中的模式，这具有 O(N) 复杂性（我在下面的实现）。

def replace_string(s, p, c):
    """
    Replace pattern p in string s with c
    :param s: initial string
    :param p: pattern to replace
    :param c: replacing string
    """
    pref = [0] * len(p)

    s_p = p + '#' + s
    p_prev = 0
    shift = 0

    for i in range(1, len(s_p)):
        k = p_prev

        while k > 0 and s_p[i] != s_p[k]:
            k = pref[k - 1]

        if s_p[i] == s_p[k]:
            k += 1

        if i < len(p):
            pref[i] = k

        p_prev = k

        if k == len(p):
            s = s[:i - 2 * len(p) + shift] + c + s[i - len(p) + shift:]
            shift += len(c) - k

    return s

然后，我使用内置 python str.replace 函数编写了相同的程序：

def replace_string_python(s, p, c):
    return s.replace(p, c)

并比较了各种字符串的性能，我将仅附上一个示例，对于长度为 1e5 的字符串：

import time


if __name__ == '__main__':
    initial_string = "a" * 100000
    pattern = "a"
    replace = "ab"

    start = time.time()
    res = replace_string(initial_string, pattern, replace)

    print(time.time() - start)

输出（我的实现）：

total time: 1.1617710590362549

输出（python内置）：

total time: 0.0015637874603271484

如您所见，通过 python str.replace 实施比 KMP 领先光年。所以我的问题是为什么？ python C代码使用什么算法？

Answer 1

虽然算法可能是 O(N)，但您的实现似乎不是线性的，至少对于模式的多次重复而言不是，因为

 s = s[:i - 2 * len(p) + shift] + c + s[i - len(p) + shift:]

这是 O(N) 本身。因此，如果您的模式在字符串中出现 N 次，那么您的实现实际上是 O(N^2).

请参阅以下算法缩放时间的计时，这证实了二次形状

LENGTH  TIME
------------
100000    1s
200000    8s
300000   31s
400000   76s
500000  134s

为什么 str.replace 这么快？

Why is str.replace so fast?

python

string

algorithm

replace

python-3.x