リストの和のリストのアルゴリズム

\(A=[a_1, a_2,a_3 ...]\)というリストあって,\(s_n = \sum_{i=1}^n a_i\)として,\(S=[s_1, s_2, s_3,...]\)というリストを新たに作りたいとする.うっかりしているとリスト内包表記を使えば早かろうと思って

def ls_comp_sum(A):
    length = len(A)
    return [sum(A[:i]) for i in range(length)]

と書いてしまったりするが,forループを使って,

def for_sum(A):
    result = [arr[0]]
    length = len(arr)
    for i in range(1, length):
        result.append(result[-1] + arr[i])
    return result

としたほうがずっと早い(Dynamic Programmingというらしい).