python - 为什么 S == S[::-1] 比循环更快？

Question

为什么检查字符串 S 是否为回文的 pythonic 方法 -- S == S[::-1] -- 比实现后？

i = 0
j = len(S) - 1
while i < j:
    if S[i] != S[j]:
        return False
    i += 1
    j -= 1
return True

Answer 1

因为 Python 代码只被编译成字节码，然后被解释。这比在 C 代码中创建一个新的反转字符串，然后将该字符串与另一个具有更多 C 代码的字符串进行比较要慢得多。

请注意，这两种算法本质上都是 O(N) 复杂度； Python 代码最多执行 1/2 N 次迭代，而字符串反转版本最多执行 2 N 次迭代，但渐近地讲这没有什么区别。

由于这两种算法都是 O(N) 线性方法，因此重要的是它们的恒定成本，即每次迭代需要多少时间。 s == s[::-1] 的固定成本大大较低。