我正在尝试找到最有效的方法来检查给定的字符串是否为回文。
首先，我尝试了运行时间为 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]
然后我对两者进行了运行时间分析。结果如下：运行时间
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
我使用的代码可以在这里访问： 运行时间表生成器
现在，我想知道为什么切片运算符（palindrome_py）的运行时间和回文函数之间存在差异。为什么我会得到这种类型的运行时间？
为什么切片算子比回文函数如此高效，幕后发生了什么？
我的观察-：运行时间与乘数成正比，即。乘数为2时的运行时间可以通过乘以CASE（n-1）的运行时间来获得，即。在这种情况下，乘数 （n） 是第 1 个，即 2
泛化，我们得到运行时间（n）=运行时间（n-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大多数时候鼓励您使用抽象并奖励您更高的性能。