リストの更新効率化 [python]

背景・目的

リストを更新していく作業の効率化を目指す。

結論

事前初期化　<　appendメソッド　<　リストの足し算

詳細

実行時間、メモリの計算にはAtCoderのコードテストを使用した。

例

動的計画法の基本問題を例にとる。

N階の建物。 $i-1$階から$i$階に向かう$A_i$段の1階分の階段と、$i-2$階から$i$階に向かう$B_i$段の2階分の階段がある。1階から$N$階に移動するには最短何段か？

import random
random.seed(0)

N = 10000
A =  [random.randint(1, 100) for _ in range(N-1)]
B =  [random.randint(1, 200) for _ in range(N-2)]

事前初期化

sec = [None] * (N+1)
sec[1] = 0
sec[2] = A[0]

for n in range(3, N+1):
  sec[n] = min(sec[n-1] + A[n-2], sec[n-2] + B[n-3])

print(sec[-1])

実行時間 58 ms
メモリ 11912 KB

appendメソッド

sec = [None]
sec.append(0)
sec.append(A[0])

for n in range(3, N+1):
  sec.append(min(sec[n-1] + A[n-2], sec[n-2] + B[n-3]))

print(sec[-1])

実行時間 61 ms
メモリ 11896 KB

足し算

sec = [None]
sec = sec + [0]
sec = sec + [A[0]]

for n in range(3, N+1):
  sec = sec + [min(sec[n-1] + A[n-2], sec[n-2] + B[n-3])]

print(sec[-1])

実行時間 3793 ms
メモリ 12648 KB

仕組み

初心者なので詳しい解説は控えるが、初期化をしておけばその要素へのアクセスのみで済むため処理が楽、appendは長さが変わるタイミングで再割り当てが起こるためやや実行時間がのび、足し算をする際には一度元のリストのコピーをするため処理が増える、というような仕組みらしい。