Python isPalindrome 之间的时间比较

Question

我在python中写了相同时间复杂度3的isPalindrome函数。但令人惊讶的是，他们的表现却大不相同。

def isPalindrome(value):
    i, j = 0, len(value) - 1
    while i < j and value[i] == value[j]:
         i, j = i + 1, j - 1
    return i >= j

def isPalindrome2(value):
    return value == value[::-1]

def isPalindrome3(value):
    res = []
    for c in value:
       res.append(c)
    return value == ''.join(res)

然后我用timeit模块测试一下

import timeit
timeit.timeit(lambda: isPalindrome('abcdefghijklmnopqrstuvzzavutsrqponmlkjihgfedcba'), number=1000000)
timeit.timeit(lambda: isPalindrome2('abcdefghijklmnopqrstuvzzavutsrqponmlkjihgfedcba'), number=1000000)
timeit.timeit(lambda: isPalindrome3('abcdefghijklmnopqrstuvzzavutsrqponmlkjihgfedcba'), number=1000000)

输出：

第一个：2.7046061150031164
第二个：0.2354857140162494
第三个：3.201262982998742

我试图找到为什么方法 2 花费的时间这么少，但找不到任何解释。请帮助我理解为什么，这将非常有帮助。

Answer 1

可能在第二种情况下，切片是由在内存中低级别工作的C代码执行的。在第一种情况下，您需要一个一个地获取元素。在第三个中，您需要迭代一个迭代器（由 for...in 语法创建）并且您需要执行需要计算和检查的追加，所有这些都用 python 代码编写。

Answer 2

要找出为什么某个函数在 Python 中更快/更慢的原因，请始终使用 dis.dis。标准 dis 模块中的 dis 函数可以反汇编函数编译成的字节码，因此您可以看到当您运行它时真正发生了什么。

下面是三个函数的反汇编：

import dis
dis.dis(isPalindrome)
  2           0 LOAD_CONST               1 (0)
              2 LOAD_GLOBAL              0 (len)
              4 LOAD_FAST                0 (value)
              6 CALL_FUNCTION            1
              8 LOAD_CONST               2 (1)
             10 BINARY_SUBTRACT
             12 ROT_TWO
             14 STORE_FAST               1 (i)
             16 STORE_FAST               2 (j)

  3          18 LOAD_FAST                1 (i)
             20 LOAD_FAST                2 (j)
             22 COMPARE_OP               0 (<)
             24 POP_JUMP_IF_FALSE       42 (to 84)
             26 LOAD_FAST                0 (value)
             28 LOAD_FAST                1 (i)
             30 BINARY_SUBSCR
             32 LOAD_FAST                0 (value)
             34 LOAD_FAST                2 (j)
             36 BINARY_SUBSCR
             38 COMPARE_OP               2 (==)
             40 POP_JUMP_IF_FALSE       42 (to 84)

  4     >>   42 LOAD_FAST                1 (i)
             44 LOAD_CONST               2 (1)
             46 BINARY_ADD
             48 LOAD_FAST                2 (j)
             50 LOAD_CONST               2 (1)
             52 BINARY_SUBTRACT
             54 ROT_TWO
             56 STORE_FAST               1 (i)
             58 STORE_FAST               2 (j)

  3          60 LOAD_FAST                1 (i)
             62 LOAD_FAST                2 (j)
             64 COMPARE_OP               0 (<)
             66 POP_JUMP_IF_FALSE       42 (to 84)
             68 LOAD_FAST                0 (value)
             70 LOAD_FAST                1 (i)
             72 BINARY_SUBSCR
             74 LOAD_FAST                0 (value)
             76 LOAD_FAST                2 (j)
             78 BINARY_SUBSCR
             80 COMPARE_OP               2 (==)
             82 POP_JUMP_IF_TRUE        21 (to 42)

  5     >>   84 LOAD_FAST                1 (i)
             86 LOAD_FAST                2 (j)
             88 COMPARE_OP               5 (>=)
             90 RETURN_VALUE

dis.dis(isPalindrome2)
  2           0 LOAD_FAST                0 (value)
              2 LOAD_FAST                0 (value)
              4 LOAD_CONST               0 (None)
              6 LOAD_CONST               0 (None)
              8 LOAD_CONST               1 (-1)
             10 BUILD_SLICE              3
             12 BINARY_SUBSCR
             14 COMPARE_OP               2 (==)
             16 RETURN_VALUE

dis.dis(isPalindrome3)
  2           0 BUILD_LIST               0
              2 STORE_FAST               1 (res)

  3           4 LOAD_FAST                0 (value)
              6 GET_ITER
        >>    8 FOR_ITER                 7 (to 24)
             10 STORE_FAST               2 (c)

  4          12 LOAD_FAST                1 (res)
             14 LOAD_METHOD              0 (append)
             16 LOAD_FAST                2 (c)
             18 CALL_METHOD              1
             20 POP_TOP
             22 JUMP_ABSOLUTE            4 (to 8)

  5     >>   24 LOAD_FAST                0 (value)
             26 LOAD_CONST               1 ('')
             28 LOAD_METHOD              1 (join)
             30 LOAD_FAST                1 (res)
             32 CALL_METHOD              1
             34 COMPARE_OP               2 (==)
             36 RETURN_VALUE

如您所见，isPalindrome2 编译的字节码比其他两个都少很多。这是因为它的大部分操作都是内置于 Python 中的，因此是用 C 编写的，而不是 Python。 isPalindrome2 中每个操作背后的 C 代码可能与其他函数之一中的 Python 代码做了类似的事情（尽管很难说），但它更快只是因为 C是一种非常快的语言，Python 非常慢。

isPalindrome2 字节码的第 4-13 字节基本上与 isPalindrome3 字节码的第 0-33 字节做同样的事情，但是 isPalindrome2 使用了很多由C 代码，而 isPalindrome3 调用 Python 函数（执行起来非常慢），额外加载常量/变量 3 次，并使用 Python for 循环。这些东西都比它们的 C 等价物慢，这意味着它更慢。第一个功能也是如此。因此，字节码少得多，主要使用C代码的第二个函数速度要快得多。

Python isPalindrome 之间的时间比较

Time Comparison between Python isPalindrome

python

string

performance

timeit