Skip to main content
 首页 » 编程设计

python之为什么某些实现在Python中运行缓慢

2025年04月02日8haluo1

我有一个函数的三种实现,用于检查字符串(或空格分隔的短语)是否是回文式:

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代码一样快,并且在大多数情况下要快得多