累積和について図を交えながら分かりやすく説明します。また累積和の応用についてのべます。難しそうだな…そうおもうかもしれませんが図をみて理解すれば、簡単です。ここを読み終わったら、きっとと累積和を使いこなせるようになるはずです。
累積和 accumulate とは
[a0, a1, a2, a3, …]とあったとき、
s0 = a0
s1 = a0 + a1 = s0 + a1
s2 = a0 + a1 + a2 = s1 + a2
s3 = a0 + a1 + a2 + a3 = s2 + a3
…
を累積和といいます。数式だと分かりにくいので図にしてみました。
s0, s1, s2, s3の幅が累積和になります。s3はa0, a1, a2, a3を足したものでありs2とa3を足したものであることが分かります。
次は具体的にみていきたいと思います。月ごとの売上と売上の累積和を表にしてみます。
月 | 売上 (百万) |
累積和 (百万) |
---|---|---|
1 | 12 | 12 |
2 | 7 | 19 |
3 | 8 | 27 |
4 | 9 | 36 |
5 | 10 | 46 |
6 | 7 | 53 |
7 | 12 | 65 |
8 | 13 | 78 |
9 | 10 | 88 |
10 | 11 | 99 |
11 | 12 | 111 |
12 | 14 | 125 |
1月は12百万円の売上があったとします。このとき1月の累積和は前月は0百万円として考えて0 + 12 = 12百万とします。
2月は7百万円の売上、累積和は前月(1月)の累積和と今月の売上を足し12 + 7 = 19百万円となります。
3月は8百万円の売上、累積和は前月(2月)の累積和と今月の売上を足し19 + 8 = 27百万円となります。
N月の累積和はN-1月までの累積和 + N月の売上で表すことができます。
以上を図にすると以下のようになります。
なぜ累積和を使うのか
ここで例えば4~6月の期間の売上はいくらになるでしょうか。単純に足し合わせて計算するのが一番簡単な方法です。 9 + 10 + 7 = 26 百万円。
では3~10月の売上はいくらでしょうか。8 + 9 + 10 + 7 + 12 + 13 + 10 + 11 = 80 百万円。
期間が長くなればなるほど計算が大変になるのがわかるとおもいます。しかし累積和を用いると引き算1回で答えを求めることができます。
4~6月の期間の売上は6月までの累積和 - 3月までの累積和 = 53 - 27 = 26百万円となります(上図参照)。
3~10月までの売上は 10月の累積和 - 2 月の累積和 = 99 - 19 = 80万円になります。
単純に足し合わせると計算する区間が長くなるにつれて計算が大変になってきますが、累積和を用いることで区間が長くても引き算1回で簡単に答えを求めることができます。
累積和 accumulate を用いて実装してみる
上記の売上の例をpythonを用いて累積和で計算してみます。期間は少し変えて8~12月の売上を集計することにします。
ffrom itertools import accumulate
sales=[0,12,7,8,9,10,7,12,13,10,11,12,14]
sales_accumulate=[i for i in accumulate(sales)]
print("累積和は")
print(sales_accumulate)
print("8~12月の売上は")
print(str(sales_accumulate[12]-sales_accumulate[8-1]))
一番最初の月の売上を求める時にリストのインデックスがマイナスにならないように一つずつずらしてインデックスが0の場所に累積和0のリストを最初にいれておきます。あとはインデックスが月に相当するようにしています。
実行結果
累積和は [0, 12, 19, 27, 36, 46, 53, 65, 78, 88, 99, 111, 125] 8~12月の売上は 60
まとめ
今回は累積和を求めるaccumulate関数を使ってみました。プログラムで区間の和を求める問題は頻出なのでうまく活用してみてください。
この記事へのコメント
コメントはまだありません。
コメントを送る