python - 为什么 `word == word[::-1]` 比 Python 中的算法解决方案更快地测试回文？

Question

我在 Code Review 上写了一个灾难性的问题，询问为什么 Python 程序员通常通过将字符串与自身进行比较来测试字符串是否为回文，而不是使用复杂度较低的算法方法，假设正常方法是快点。

这是 pythonic 方式:

def is_palindrome_pythonic(word):
    # The slice requires N operations, plus memory
    # and the equality requires N operations in the worst case
    return word == word[::-1]

这是我尝试用一​​种更有效的方法来实现这一点:

def is_palindrome_normal(word):
    # This requires N/2 operations in the worst case
    low = 0
    high = len(word) - 1
    while low < high:
        if word[low] != word[high]:
            return False
        low += 1
        high -= 1
    return True

我希望正常方式会比 pythonic 方式更快。参见示例 this great article

然而，使用 timeit 对其进行计时会带来完全相反的结果:

setup = '''
def is_palindrome_pythonic(word):
    # ...

def is_palindrome_normal(word):
    # ...

# N here is 2000
first_half = ''.join(map(str, (i for i in range(1000))))
word = first_half + first_half[::-1]
'''

timeit.timeit('is_palindrome_pythonic(word)', setup=setup, number=1000)
# 0.0052

timeit.timeit('is_palindrome_normal(word)', setup=setup, number=1000)
# 0.4268

然后我发现我的n太小了，所以我把word的长度从2000改成了2,000,000。 pythonic 方式平均耗时约 16 秒，而正常方式运行几分钟后我取消了它。

顺便说一下，在最好的情况下，第一个字母与最后一个字母不匹配，普通算法要快得多。

如何解释两种算法速度之间的极端差异？

Answer 1

因为带有切片的“Pythonic”方式是在 C 中实现的。解释器/VM 不需要执行超过大约一次。大部分算法都用在 native 代码的紧密循环中。