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

Question

为什么检查字符串 S 是否为回文的 pythonic 方法比以下实现更快？

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

Answer 1

以下不是很好的基准测试，但每次我运行你的函数都比 s == s[::-1] 稍微慢。我还尝试更改执行顺序（运行你的函数在前），它仍然提供相同的结果！

import timeit

def is_pali1(s):
    s = str(s)
    return s == s[::-1]


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

res = timeit.repeat("for x in range(99999900,100000000): is_pali1(x)", "from __main__ import is_pali1", number=100000)
print "is_pali1", sum(res)/len(res)
res = timeit.repeat("for x in range(99999900,100000000): is_pali2(x)", "from __main__ import is_pali2", number=100000)
print "is_pali2", sum(res)/len(res)

输出

is_pali1 4.37230348587
is_pali2 4.67844009399

请注意，我在两个函数中都将数字修改为字符串：s = str(s) 这样就不会影响结果。 在 Python 2.7.6.

上测试

Answer 2

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

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

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

的固定成本 大大降低

Answer 3

S == S[::-1] 在最坏的情况下会很快，因为在这种情况下，C 中的一切都是运行，与基于 Python 的循环相比，这将快如闪电。您的版本的唯一优点是它不会在开始比较之前等待反向字符串的创建，因此在那些情况下 ^* 对于大字符串 S == S[::-1] 将实际上很慢。

我们可以改进 S == S[::-1] 一点，如果不是比较整体，而是取字符串的前半部分和后半部分的一部分，并将前半部分与后半部分的反向版本进行比较。

def fast_half(S):
    length = len(S)
    half = length/2
    first, last = half + (length % 2), half
    return S[:first] == S[last:][::-1]

def fast_simple(S):
    return S == S[::-1]

让我们比较一下：

>>> S = 'A' * 10**5
>>> %timeit fast_simple(S)
10000 loops, best of 3: 88.7 µs per loop
>>> %timeit fast_half(S)
10000 loops, best of 3: 49.1 µs per loop
>>> S = 'A' * 10**6
>>> %timeit fast_simple(S)
1000 loops, best of 3: 1.03 ms per loop
>>> %timeit fast_half(S)
1000 loops, best of 3: 601 µs per loop

我们可以通过取上半部分的 memoryview 使 fast_half 稍微快一些，对于下半部分这是不可能的，因为内存视图不支持扩展切片。而且它们只适用于 str(bytes in Python 3) 和 bytearrays.

def fast_half_memoryview(S):
    length = len(S)
    half = length/2
    first, last = half + (length % 2), half
    return memoryview(S)[:first] == S[last:][::-1]

>>> S = 'A' * 10**5
>>> %timeit fast_half_memoryview(S)
10000 loops, best of 3: 46 µs per loop
>>> S = 'A' * 10**6
>>> %timeit fast_half_memoryview(S)
1000 loops, best of 3: 523 µs per loop
>>> S = 'A' * 10**7
>>> %timeit fast_half(S)
100 loops, best of 3: 12.8 ms per loop
>>> %timeit fast_half_memoryview(S)
100 loops, best of 3: 10.8 ms per loop
>>> %timeit fast_simple(S)
100 loops, best of 3: 17.3 ms per loop

对于小字符串 S == S[::-1] 是最好的：

>>> S = 'A' * 10
>>> %timeit fast_half(S)
1000000 loops, best of 3: 721 ns per loop
>>> %timeit fast_half_memoryview(S)
1000000 loops, best of 3: 1.07 µs per loop
>>> %timeit fast_simple(S)
1000000 loops, best of 3: 353 ns per loop
>>> %timeit func(S)  # OP's code
1000000 loops, best of 3: 1.34 µs per loop

^* 当创建反转字符串或切片会减慢我们的速度时：

>>> S = 'A' * 10**6 + 'a'
>>> %timeit fast_simple(S)
1000 loops, best of 3: 976 µs per loop
>>> %timeit fast_half(S)
1000 loops, best of 3: 566 µs per loop
>>> %timeit fast_half_memoryview(S)
1000 loops, best of 3: 523 µs per loop
>>> %timeit func(S)
1000000 loops, best of 3: 382 ns per loop

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

Why is S == S[::-1] faster than looping?

python

string

performance

palindrome