为什么某些实现 运行 在 Python 中变慢？
Why do certain implementations run slow in Python?
我有一个函数的三个实现，用于检查字符串（或 space 定界短语）是否为回文：
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 说 "no, no, no, you have to run with 20kg on your shoulders"。圈数越多（即要执行的字节码越多），速度就越慢。一般来说，这种性能下降在 CPython 中应该是线性的，但如果不通读 CPython 的代码谁知道呢？我听说应该在 CPython 中实现一种名为 inline caching 的技术，这会极大地影响性能。不知道做了没有。
另一件事是 Python 中的调用很昂贵。关于如何在低级别完成调用（即将寄存器压入堆栈并执行跳转）有 ABI。 C/C++ 紧随其后。现在 Python 做的远不止这些。创建了帧（可以对其进行分析，例如，当发生异常时）、最大递归检查等。所有这些都会导致性能下降。
所以 palindrome 函数执行 很多 次调用。 Python 中的递归效率低下。特别是这就是 palindrome2 比 palindrome1.
更快的原因
另一件事是 palindrome1 有 [::-1] 转换成 BUILD_SLICE 在 C 中实现的调用。所以即使它做了更多必要的（没有理由创建字符串的另一个副本）它仍然比其他函数更快，因为中间层（即字节码）是最小的。编译器不需要浪费时间在字节码解释上。
另一件重要的事情是，您在 Python 中创建的每个对象都必须进行垃圾回收。而且由于这些对象通常比纯 C 对象大（例如由于引用计数器），所以这需要更多时间。啊，顺便说一下，引用计数器的递增和递减也需要时间。还有一个叫做 GIL（全局解释器锁）的东西，它在每个命令中获取和释放一个锁，以便字节码是线程安全的。即使对于单线程应用程序来说完全没有必要。但是 Python 不知道您在某些时候不会 运行 线程，它每次都必须这样做。这一切都是为了让您不必担心大多数 C/C++ 编码人员必须处理的难题。 :)
现在 PyPy 是另一回事了。它内部有一个简洁的东西，叫做 JIT = Just In Time 编译器。它的作用是获取任何 Python 字节码并将其动态转换为机器码，然后再使用。所以对函数的初始调用有这种编译开销，但它仍然更快。最终根本没有字节码，所有函数 运行 都纯粹在 CPU 上。然而，这并不意味着 PyPy 与用 C 编写的函数一样快（例如 [::-1]）。仅仅因为有很多在 C 级别完成的优化，我们不知道如何在 PyPy 或任何其他 Python 解释器中实现。这是由于语言的性质——它是动态的。现在是否真的不可能是另一回事，一点也不明显，但目前我们只是不知道该怎么做。
tl;dr; 内建函数（或更普遍的 Python 中的 C 代码 运行）总是至少与等效的纯 Python 代码并且在大多数情况下速度更快
我有一个函数的三个实现，用于检查字符串（或 space 定界短语）是否为回文：
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 说 "no, no, no, you have to run with 20kg on your shoulders"。圈数越多（即要执行的字节码越多），速度就越慢。一般来说，这种性能下降在 CPython 中应该是线性的，但如果不通读 CPython 的代码谁知道呢？我听说应该在 CPython 中实现一种名为 inline caching 的技术，这会极大地影响性能。不知道做了没有。
另一件事是 Python 中的调用很昂贵。关于如何在低级别完成调用（即将寄存器压入堆栈并执行跳转）有 ABI。 C/C++ 紧随其后。现在 Python 做的远不止这些。创建了帧（可以对其进行分析，例如，当发生异常时）、最大递归检查等。所有这些都会导致性能下降。
所以 palindrome 函数执行 很多 次调用。 Python 中的递归效率低下。特别是这就是 palindrome2 比 palindrome1.
另一件事是 palindrome1 有 [::-1] 转换成 BUILD_SLICE 在 C 中实现的调用。所以即使它做了更多必要的（没有理由创建字符串的另一个副本）它仍然比其他函数更快，因为中间层（即字节码）是最小的。编译器不需要浪费时间在字节码解释上。
另一件重要的事情是，您在 Python 中创建的每个对象都必须进行垃圾回收。而且由于这些对象通常比纯 C 对象大（例如由于引用计数器），所以这需要更多时间。啊，顺便说一下，引用计数器的递增和递减也需要时间。还有一个叫做 GIL（全局解释器锁）的东西，它在每个命令中获取和释放一个锁，以便字节码是线程安全的。即使对于单线程应用程序来说完全没有必要。但是 Python 不知道您在某些时候不会 运行 线程，它每次都必须这样做。这一切都是为了让您不必担心大多数 C/C++ 编码人员必须处理的难题。 :)
现在 PyPy 是另一回事了。它内部有一个简洁的东西，叫做 JIT = Just In Time 编译器。它的作用是获取任何 Python 字节码并将其动态转换为机器码，然后再使用。所以对函数的初始调用有这种编译开销，但它仍然更快。最终根本没有字节码，所有函数 运行 都纯粹在 CPU 上。然而，这并不意味着 PyPy 与用 C 编写的函数一样快（例如 [::-1]）。仅仅因为有很多在 C 级别完成的优化，我们不知道如何在 PyPy 或任何其他 Python 解释器中实现。这是由于语言的性质——它是动态的。现在是否真的不可能是另一回事，一点也不明显，但目前我们只是不知道该怎么做。
tl;dr; 内建函数（或更普遍的 Python 中的 C 代码 运行）总是至少与等效的纯 Python 代码并且在大多数情况下速度更快