我有一个函数的三种实现,用于检查字符串(或空格分隔的短语)是否是回文式:
def palindrome(str_in):
def p(s, i, j):
if i >= j:
return True
elif s[i] != s[j]:
return False
else:
return p(s, i+1, j-1)
return p(str_in.replace(' ', '').lower(), 0, len(str_in)-1)
def palindrome1(s):
st = s.replace(' ', '').lower()
return st == st[::-1]
def palindrome2(s):
st = s.replace(' ', '').lower()
i, j = 0, len(st)-1
while i < j:
if st[i] != st[j]:
return False
else:
i += 1
j -= 1
return True
现在,我认为
palindrome()
在理论上是最佳的,因为不会发生反转并且不会发生额外的内存,但是python没有尾调用优化。 palindrome2()
是palindrome()
的命令性版本,但仍比palindrome1()
花费更长的时间。为什么是这样?以下是分析结果(运行:
python -m cProfile file.py
): 12 function calls in 45.341 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.232 0.232 45.341 45.341 file.py:1(<module>)
1 2.198 2.198 3.532 3.532 file.py:300(palindrome1)
1 39.442 39.442 40.734 40.734 file.py:304(palindrome2)
1 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
2 2.396 1.198 2.396 1.198 {method 'lower' of 'str' objects}
1 0.843 0.843 0.843 0.843 {method 'read' of 'file' objects}
2 0.231 0.115 0.231 0.115 {method 'replace' of 'str' objects}
1 0.000 0.000 0.000 0.000 {open}
1 0.000 0.000 0.000 0.000 {sys.setrecursionlimit}
这是分析结果(运行:
pypy -m cProfile hw2.py
): 11 function calls in 12.470 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.011 0.011 12.470 12.470 hw2.py:1(<module>)
1 2.594 2.594 6.280 6.280 hw2.py:303(palindrome1)
1 0.852 0.852 4.347 4.347 hw2.py:307(palindrome2)
1 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
2 3.263 1.631 3.263 1.631 {method 'lower' of 'str' objects}
1 1.832 1.832 1.832 1.832 {method 'read' of 'file' objects}
2 3.918 1.959 3.918 1.959 {method 'replace' of 'str' objects}
1 0.000 0.000 0.000 0.000 {sys.setrecursionlimit}
这是我的回文构造函数:
def palindrome_maker(n):
from random import choice
alphabet = ' abcdefghijklmnopqrstuvwxyz'
front = ''.join([choice(alphabet) for _ in range(n//2)])
back = front[::-1]
return front + (choice(alphabet) if n%2==1 else '') + back
顺便说一句:该配置文件显示了调用长度为
999999999
的字符串的函数的性能。
最佳答案
好的,让我们从头开始讨论。 CPython将可见的文本编译为字节码,这是一种表示形式,虚拟机(即解释器)更容易理解。
由于此开销,palindrome
和palindrome2
函数都比palindrome1
慢。 CPython中有一个名为dis
的简洁模块。如果在编译函数上使用它,它将显示其内部表示。因此,让我们这样做:
>>> dis.dis(palindrome)
2 0 LOAD_CLOSURE 0 (p)
3 BUILD_TUPLE 1
6 LOAD_CONST 1 (<code object p at 0x01B95110, file "<stdin>", line 2>)
9 LOAD_CONST 2 ('palindrome.<locals>.p')
12 MAKE_CLOSURE 0
15 STORE_DEREF 0 (p)
9 18 LOAD_DEREF 0 (p)
21 LOAD_FAST 0 (str_in)
24 LOAD_ATTR 0 (replace)
27 LOAD_CONST 3 (' ')
30 LOAD_CONST 4 ('')
33 CALL_FUNCTION 2 (2 positional, 0 keyword pair)
36 LOAD_ATTR 1 (lower)
39 CALL_FUNCTION 0 (0 positional, 0 keyword pair)
42 LOAD_CONST 5 (0)
45 LOAD_GLOBAL 2 (len)
48 LOAD_FAST 0 (str_in)
51 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
54 LOAD_CONST 6 (1)
57 BINARY_SUBTRACT
58 CALL_FUNCTION 3 (3 positional, 0 keyword pair)
61 RETURN_VALUE
现在让我们将其与
palindrome1
函数进行比较:>>> dis.dis(palindrome1)
2 0 LOAD_FAST 0 (s)
3 LOAD_ATTR 0 (replace)
6 LOAD_CONST 1 (' ')
9 LOAD_CONST 2 ('')
12 CALL_FUNCTION 2 (2 positional, 0 keyword pair)
15 LOAD_ATTR 1 (lower)
18 CALL_FUNCTION 0 (0 positional, 0 keyword pair)
21 STORE_FAST 1 (st)
3 24 LOAD_FAST 1 (st)
27 LOAD_FAST 1 (st)
30 LOAD_CONST 0 (None)
33 LOAD_CONST 0 (None)
36 LOAD_CONST 4 (-1)
39 BUILD_SLICE 3
42 BINARY_SUBSCR
43 COMPARE_OP 2 (==)
46 RETURN_VALUE
因此,这就是CPython或多或少看到的(实际上,它们被编码为二进制形式,目前不相关)。然后,虚拟机遍历这些行并逐一执行它们。
因此,第一个显而易见的事情是:更多的行==更多的执行时间。这是因为必须解释每一行并且必须执行适当的C代码。由于循环和递归调用,除了
palindrome1
以外,两个函数中都有很多行执行。因此,从本质上讲,这就像您尝试跑几圈,但Python表示“不,不,不,您必须肩负20公斤的重量”。圈数越多(即执行的字节码越多),您获得的速度就越慢。通常,这种性能下降在CPython中应该是线性的,但是真的有谁知道而无需阅读CPython的代码?我听说应该在CPython中实现一种称为inline caching的技术,这会大大影响性能。我不知道它是否完成。另一件事是,Python中的调用非常昂贵。 ABI给出了如何在低层进行调用(即将寄存器压入堆栈并进行跳转)。 C / C ++紧随其后。现在,Python的功能远不止这些。创建了一些帧(可以进行分析(例如,在发生异常时进行分析),最大递归检查等),所有这些都将导致性能损失。
因此
palindrome
函数可以进行大量调用。递归在Python中效率低下。特别是这就是为什么palindrome2
比palindrome1
更快的原因。另一件事是
palindrome1
具有[::-1]
可以转换为用C实现的BUILD_SLICE
调用。因此,尽管这样做的必要性更高(没有理由创建字符串的另一个副本),但它仍然更快那么其他功能仅仅是因为中间层(即字节码)最小。编译器无需在字节码解释上浪费时间。另一个重要的事情是,必须用垃圾回收您在Python中创建的每个对象。并且由于这些对象通常比纯C对象大(例如,由于引用计数器),因此花费更多时间。嗯,顺便说一下,增加和减少参考计数器也要花费时间。还有一个叫做GIL(全局解释器锁)的东西,它在每个命令处获取并释放一个锁,以便字节码是线程安全的。即使对于单线程应用程序完全没有必要。但是Python不知道您不会在某个时候运行线程,它每次都必须这样做。这就是所有这些,因此您不必担心大多数C / C ++编码人员必须处理的棘手问题。 :)
现在,PyPy是另一个故事。它内部有一个名为JIT = Just In Time的编译器。它需要做什么,它需要任何Python字节码并将其即时转换为机器代码,然后可以重复使用。因此,对函数的初始调用具有此编译开销,但是它仍然更快。最终根本没有字节码,所有功能都完全在CPU上运行。但是,这并不意味着PyPy的速度与用C编写的函数一样快(例如
[::-1]
)。仅仅因为有很多优化是在C级别上完成的,我们不知道如何在PyPy或任何其他Python解释器中实现。这是由于语言的性质-它是动态的。现在,是否真的不可能是另外一个故事,这一点也不明显,但是目前我们还不知道该怎么做。tl; dr;内置函数(或更一般地说,在Python中运行的C代码)总是至少与同等的纯Python代码一样快,并且在大多数情况下要快得多
关于python - 为什么某些实现在Python中运行缓慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39420734/