Почему .append () медленнее, чем установка значения в предварительно выделенном массиве?

Question

Я пытаюсь ускорить часть моего кода, которая включает в себя циклический просмотр и установку значений в большом двумерном массиве.Одним из предложений было то, что я пытаюсь предварительно выделить массив, а не использовать .append (), но было отмечено, что в Python .append () является амортизированной операцией O (1).

Однако, когда я тестировал его, используя следующий код:

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)

Я получаю предварительно выделенный массив, занимающий на 3-4 секунды меньше, чем массив, который не был предварительно выделен (~ 17 спо сравнению с ~ 21).Что в этом коде заставляет основанную на .append () функцию занимать больше времени, чем замена значения в предварительно выделенном массиве?

Answer 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

То, как вы подходите к вещам, может иметь огромное значение.

Answer 2

.append () может заставить python выделять больше памяти, что занимает много времени.Используя распределенную структуру, вы экономите время, чтобы выполнить все отдельные распределения.