我在 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 秒,而正常方式运行几分钟后我取消了它。
顺便说一下,在最好的情况下,第一个字母与最后一个字母不匹配,普通算法要快得多。
如何解释两种算法速度之间的极端差异?
最佳答案
因为带有切片的“Pythonic”方式是在 C 中实现的。解释器/VM 不需要执行超过大约一次。大部分算法都用在 native 代码的紧密循环中。
关于python - 为什么 `word == word[::-1]` 比 Python 中的算法解决方案更快地测试回文?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40580558/