Pythonのitertools.accumulate関数で累積和（プレフィックスサム）配列を作る方法

Pythonでは、リスト（配列）の累積和（プレフィックスサム）を簡単に求めることができます。標準ライブラリのitertoolsモジュールに含まれるaccumulate()関数を使えば、先頭の要素から順に値を加算していった「走査合計（ランニングトータル）」を返すイテレータを生成できます。

itertools.accumulate(iterable[, func])は、モジュール内の他の関数と同様に、イテレータを構築して返します。そのため、取得したイテレータにはforループやlist()など、ストリームを消費する処理を通じてアクセスします。デフォルトの動作は要素の合計（加算）ですが、扱える要素はDecimalやFractionを含む任意の「加算可能な型」です。さらに、オプションの第2引数として2引数の関数を渡すと、加算の代わりにその関数が使われるため、累積積やカスタム演算にも対応できます。

実行例

入力:
data = [1, 0, 2, 3, 5]
>>> list(accumulate(data))     # 累積合計

出力:
[1, 1, 3, 6, 11]

この例では、先頭から順に「1」「1+0」「1+0+2」「1+0+2+3」「1+0+2+3+5」が計算され、各時点までの合計がリストとして得られます。

アルゴリズム

ステップ1: リストを作成する。
ステップ2: list(accumulate()) を使い、累積合計を取得する。
ステップ3: 結果を表示する。

サンプルコード

# accumulate関数を使って
# 累積和（プレフィックスサム）配列を出力するPythonプログラム
from itertools import accumulate

def summation(A):
    print("合計後のリスト ::>", list(accumulate(A)))

# メインプログラム
if __name__ == "__main__":
    A = []
    n = int(input("最初のリストのサイズを入力してください ::"))
    print("最初のリストの要素を入力してください ::")
    for i in range(n):
        k = int(input(""))
        A.append(k)
    summation(A)

出力結果

最初のリストのサイズを入力してください ::5
最初のリストの要素を入力してください ::
1
2
3
4
5
合計後のリスト ::> [1, 3, 6, 10, 15]

このように、ユーザーが入力した5つの要素「1, 2, 3, 4, 5」に対して、累積和「1, 3, 6, 10, 15」が順に出力されます。accumulate()を活用すれば、ループを自前で書くことなく簡潔にプレフィックスサム配列を実装できるのが大きなメリットです。