Python low-level vs high-level performance(回文函数运行时分析)

Question

我试图找到最有效的方法来检查给定的字符串是否为回文。
首先，我尝试了蛮力，其运行时间为 O(N)。然后我通过只进行 n/2 次比较而不是 n 次来稍微优化代码。

代码如下:

def palindrome(a):
    length=len(a)
    iterator=0
    while iterator <= length/2:
        if a[iterator]==a[length-iterator-1]:
            iterator+=1
        else:
            return False

    return True

与蛮力相比，它只需要一半的时间，但仍然是 O(N) 的阶数。

同时，我也想到了一个使用切片算子的方案。
这是代码:

def palindrome_py(a):
    return a==a[::-1]  

然后我对两者都进行了运行时分析。这是结果: Running time

Length of string used is 50
Length multiplier indicates length of new string(50*multiplier)
Running time for 100000 iterations  

For palindrome    For palindrome_py   Length Multiplier
0.6559998989       0.5309998989       1
1.2970001698       0.5939998627       2
3.5149998665       0.7820000648       3
13.4249999523       1.5310001373       4
65.5319998264       5.2660000324       5

我使用的代码可以在这里访问:Running Time Table Generator

现在，我想知道为什么切片运算符(palindrome_py)和回文函数的运行时间存在差异。为什么我得到这种类型的运行时间？
为什么切片运算符与回文函数相比如此高效，幕后发生了什么？

我的观察-:运行时间与乘数成正比，即。乘数为2时的运行时间可以通过乘以情况(n-1)的运行时间即得到。在这种情况下，第一乘数 (n) 即 2

归纳起来，我们得到运行时间(n)=运行时间(n-1)*乘数

Answer 1

您的基于切片的解决方案仍然是 O(n)，常数变得更小(这是您的乘数)。它更快，因为用 Python 完成的事情更少，而用 C 完成的事情更多。字节码显示了这一切。

In [1]: import dis

In [2]: %paste
def palindrome(a):
    length=len(a)
    iterator=0
    while iterator <= length/2:
        if a[iterator]==a[length-iterator-1]:
            iterator+=1
        else:
            return False

    return True

## -- End pasted text --

In [3]: dis.dis(palindrome)
  2           0 LOAD_GLOBAL              0 (len)
              3 LOAD_FAST                0 (a)
              6 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
              9 STORE_FAST               1 (length)

  3          12 LOAD_CONST               1 (0)
             15 STORE_FAST               2 (iterator)

  4          18 SETUP_LOOP              65 (to 86)
        >>   21 LOAD_FAST                2 (iterator)
             24 LOAD_FAST                1 (length)
             27 LOAD_CONST               2 (2)
             30 BINARY_TRUE_DIVIDE
             31 COMPARE_OP               1 (<=)
             34 POP_JUMP_IF_FALSE       85

  5          37 LOAD_FAST                0 (a)
             40 LOAD_FAST                2 (iterator)
             43 BINARY_SUBSCR
             44 LOAD_FAST                0 (a)
             47 LOAD_FAST                1 (length)
             50 LOAD_FAST                2 (iterator)
             53 BINARY_SUBTRACT
             54 LOAD_CONST               3 (1)
             57 BINARY_SUBTRACT
             58 BINARY_SUBSCR
             59 COMPARE_OP               2 (==)
             62 POP_JUMP_IF_FALSE       78

  6          65 LOAD_FAST                2 (iterator)
             68 LOAD_CONST               3 (1)
             71 INPLACE_ADD
             72 STORE_FAST               2 (iterator)
             75 JUMP_ABSOLUTE           21

  8     >>   78 LOAD_CONST               4 (False)
             81 RETURN_VALUE
             82 JUMP_ABSOLUTE           21
        >>   85 POP_BLOCK

 10     >>   86 LOAD_CONST               5 (True)
             89 RETURN_VALUE

有很多 Python 虚拟机级指令，它们基本上是函数调用，在 Python 中非常昂贵。

现在，第二个函数是什么。

In [4]: %paste
def palindrome_py(a):
    return a==a[::-1]

## -- End pasted text --

    In [5]: dis.dis(palindrome_py)
      2           0 LOAD_FAST                0 (a)
                  3 LOAD_FAST                0 (a)
                  6 LOAD_CONST               0 (None)
                  9 LOAD_CONST               0 (None)
                 12 LOAD_CONST               2 (-1)
                 15 BUILD_SLICE              3
                 18 BINARY_SUBSCR
                 19 COMPARE_OP               2 (==)
                 22 RETURN_VALUE

此处不涉及 Python 迭代(跳线)，您只有 3 次调用(这些指令调用方法):BUILD_SLICE、BINARY_SUBSCR、COMPARE_OP ，全部用 C 完成，因为 str 是一个内置类型，所有方法都用 C 编写。公平地说，我们在第一个函数中看到了相同的指令(以及更多其他指令) ), 但它们对每个字符重复，将方法调用开销乘以 n。在这里你只需支付 Python 的函数调用开销一次，其余的都在 C 中完成。

底线。你不应该手动在 Python 中做低级的事情，因为它会比高级的对手运行得慢(除非你有一个渐近更快的替代方案，它确实需要低级的魔法)。 Python 与许多其他语言不同，大多数时候鼓励您使用抽象并以更高的性能奖励您。