为什么“word == word[::-1]"比 Python 中的算法解决方案更快地测试回文? [英] Why is `word == word[::-1]` to test for palindrome faster than a more algorithmic solution in Python?

问题描述

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

I wrote a disaster of a question on Code Review asking why Python programmers normally test if a string is a palindrome by comparing the string to itself reversed, instead of a more algorithmic way with lower complexity, assuming that the normal way would be faster.

这是pythonic方式:

Here is the pythonic way:

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]

这是我尝试以更有效的方式来实现这一点:

Here is my attempt at a more efficient way to accomplish this:

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 方式更快.参见例如这篇很棒的文章

I would expect the normal way would be faster than the pythonic way. See for example this great article

用 timeit 计时，结果正好相反:

Timing it with timeit, however, brought exactly the opposite result:

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秒左右，而正常方式运行几分钟前我取消了.

I then figured that my n was too small, so I changed the length of word from 2000 to 2,000,000. The pythonic way took about 16 seconds on average, whereas the normal way ran several minutes before I canceled it.

顺便说一句，在第一个字母与最后一个字母不匹配的最佳情况下，正常算法要快得多.

Incidentally, in the best case scenario, where the very first letter does not match the very last letter, the normal algorithm was much faster.

是什么解释了两种算法的速度之间的巨大差异?

What explains the extreme difference between the speeds of the two algorithms?

推荐答案

因为带有切片的Pythonic"方式是在 C 中实现的.解释器/VM 不需要执行超过大约一次.大部分算法都花在了原生代码的紧密循环中.

Because the "Pythonic" way with slicing is implemented in C. The interpreter / VM doesn't need to execute more than approximately once. The bulk of the algorithm is spent in a tight loop of native code.

这篇关于为什么“word == word[::-1]"比 Python 中的算法解决方案更快地测试回文?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！