为什么.append（）比在预分配数组中设置值慢？

我想加快我的代码的一部分，涉及循环和设置一个大的二维数组中的值。其中一个建议是，我尝试预先分配数组而不是使用.append（），但它指出在Python中，.append（）是一个摊销O（1）操作。为什么.append（）比在预分配数组中设置值慢？

然而，当我测试使用以下代码：

import time 

x = list() 
z = list() 
t1 = time.time() 
for i in range(10000): 
    z.append([]) 
    for j in range(10000): 
     z[i].append(0) 

t1 = time.time() 
for i in range(10000): 
    x.append([]) 
    for j in range(10000): 
     x[i].append(1) 
print(time.time()-t1) 

t1 = time.time() 
for i in range(10000): 
    for j in range(10000): 
     z[i][j] = 1 
print(time.time()-t1)

我consitently得到相比〜21预先分配的阵列以3-4秒小于未预分配的阵列（〜17S ）。这段代码中的基于.append（）的函数花费的时间比替换预分配数组中的值要长吗？

来源

2012-01-20 MDT

“摊销O（1）”表示当你考虑对象的整个生命周期时，它是O（1），而不仅仅是任何追加本身，这就是你在这里做的。就像任何毫无意义的基准一样，除非你对整个项目进行简介并证明它很重要，否则这并不重要。 –

我对Python没有多少了解，但是对于大多数编程语言来说，追加到一个数组（在内存中必须是连续的）通常意味着必须腾出空间来扩展数组，这样每次追加都需要额外的时间。 –

@NicFoster：动态数组的容量很少被扩展为1，它更可能是当前容量的一半或两倍或类似的东西（这是分摊的东西来自哪里）。 –

考虑以下几点：

from dis import dis 

def f1(): 
x = [] 
for i in range(10000): 
    x.append([]) 
    for j in range(10000): 
    x[i].append(0) 
return x 

dis(f1) 

    2   0 BUILD_LIST    0 
       3 STORE_FAST    0 (x) 

    3   6 SETUP_LOOP    73 (to 82) 
       9 LOAD_GLOBAL    0 (range) 
      12 LOAD_CONST    1 (10000) 
      15 CALL_FUNCTION   1 
      18 GET_ITER 
     >> 19 FOR_ITER    59 (to 81) 
      22 STORE_FAST    1 (i) 

    4   25 LOAD_FAST    0 (x) 
      28 LOAD_ATTR    1 (append) 
      31 BUILD_LIST    0 
      34 CALL_FUNCTION   1 
      37 POP_TOP 

    5   38 SETUP_LOOP    37 (to 78) 
      41 LOAD_GLOBAL    0 (range) 
      44 LOAD_CONST    1 (10000) 
      47 CALL_FUNCTION   1 
      50 GET_ITER 
     >> 51 FOR_ITER    23 (to 77) 
      54 STORE_FAST    2 (j) 

    6   57 LOAD_FAST    0 (x) 
      60 LOAD_FAST    1 (i) 
      63 BINARY_SUBSCR 
      64 LOAD_ATTR    1 (append) 
      67 LOAD_CONST    2 (0) 
      70 CALL_FUNCTION   1 
      73 POP_TOP 
      74 JUMP_ABSOLUTE   51 
     >> 77 POP_BLOCK 
     >> 78 JUMP_ABSOLUTE   19 
     >> 81 POP_BLOCK 

    7  >> 82 LOAD_FAST    0 (x) 
      85 RETURN_VALUE

则为：

def f2(): 
x = list() 
for i in range(10000): 
    x.append([0]*10000) 
return x 

dis(f2) 

    2   0 LOAD_GLOBAL    0 (list) 
       3 CALL_FUNCTION   0 
       6 STORE_FAST    0 (x) 

    3   9 SETUP_LOOP    40 (to 52) 
      12 LOAD_GLOBAL    1 (range) 
      15 LOAD_CONST    1 (10000) 
      18 CALL_FUNCTION   1 
      21 GET_ITER 
     >> 22 FOR_ITER    26 (to 51) 
      25 STORE_FAST    1 (i) 

    4   28 LOAD_FAST    0 (x) 
      31 LOAD_ATTR    2 (append) 
      34 LOAD_CONST    2 (0) 
      37 BUILD_LIST    1 
      40 LOAD_CONST    1 (10000) 
      43 BINARY_MULTIPLY 
      44 CALL_FUNCTION   1 
      47 POP_TOP 
      48 JUMP_ABSOLUTE   22 
     >> 51 POP_BLOCK 

    5  >> 52 LOAD_FAST    0 (x) 
      55 RETURN_VALUE

问题的方式可以使一个巨大的差异。

来源

2012-01-20 03:22:57

谢谢，这真的显示出不同。未来将会使用dis模块更多地研究事物。 – MDT

.append（）会导致python分配更多的内存，这需要时间。通过使用每个分配的结构，您可以节省时间来完成所有的单个分配。

来源

2012-01-20 03:23:00

为什么.append（）比在预分配数组中设置值慢？

回答

相关问题