爲什麼.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（）比在預分配數組中設置值慢？

回答

相關問題