累積和は、「適切な前処理をおこない、配列上の区間の総和を高速で処理できるようにする手法」です。累積和を利用することで配列上の区間の総和がどれくらい速く計算できるようになるのかを検証します。
区間の和を求める
第一問
https://paiza.jp/works/mondai/prefix_sum_problems/prefix_sum_problems__section_sum_step1
10 個の整数 a_0, a_1, a_2, …, a_9 からなる数列 a が与えられるが、この数列の a_2 から a_7 までの和はどうなるだろうか？
累積和をつかわず普通にa[2]からa[7]までを足したほうが速そうですが、累積和を使うとこうなります。当然のことながら計算結果は同じになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
using System; using System.Linq; class Program { static void Main() { string s = "1 5 9 7 5 3 2 5 8 4"; int[] vs = s.Split().Select(_ => int.Parse(_)).ToArray(); //vs[2]からvs[7]までの総和を普通に計算する int ret = 0; for (int i = 2; i <= 7; i++) { ret += vs[i]; } Console.WriteLine(ret); //vs[2]からvs[7]までの総和を累積和を使って計算する int[] sn = new int[vs.Length]; for (int i = 0; i < vs.Length; i++) { if (i == 0) sn[i] = vs[0]; else sn[i] = sn[i - 1] + vs[i]; } Console.WriteLine(sn[7] - sn[2 - 1]); } } |
これだけだとあまり便利さがわかりません。普通に計算したほうが速そうです。
ではこれだとどうでしょうか？
連続する3つの数の和を取得する
https://paiza.jp/works/mondai/prefix_sum_problems/prefix_sum_problems__sum_max_step1
i番目までの総和から(i-3)番目までの総和を引くことでる3つの数の和を知ることができます。高校の数学で自然数の総和の公式を習いますが、1からではなく途中の数からの場合、（bまでの総和）-（aまでの総和）で（a+1）からbまでの総和を求めることができます。似たような方法をここで使います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
using System; using System.Linq; class Program { static void Test1() { // 文字列は標準入力から "0 1 2 3" のように半角スペース区切りで渡される int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); // 連続する3つの数の和を取得する // 累積和を取得する System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); sw.Start(); int[] sn = new int[vs.Length]; for (int i = 0; i < vs.Length; i++) { if (i == 0) sn[i] = vs[0]; else sn[i] = sn[i - 1] + vs[i]; } int max = sn[2]; for (int i = 3; i < sn.Length; i++) { if (max < sn[i] - sn[i - 3]) max = sn[i] - sn[i - 3]; } Console.WriteLine(max); sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds); } static void Test2() { // 文字列は標準入力から "0 1 2 3" のように半角スペース区切りで渡される int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); // 連続する3つの数の和を愚直に取得する System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); sw.Start(); int max = vs[0] + vs[1] + vs[2]; for (int i = 0; i + 2 < vs.Length; i++) { if (max < vs[i] + vs[i + 1] + vs[i + 2]) max = vs[i] + vs[i + 1] + vs[i + 2]; } Console.WriteLine(max); sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds); } static void Main() { // Test1()またはTest2()を呼び出す } } |
System.Diagnostics.Stopwatchをつかって実行時間を計測していますが、両者ほとんど変わりません。
連続するk個の和
こんな問題もあります。
https://paiza.jp/works/mondai/prefix_sum_problems/prefix_sum_problems__sum_max_boss
問題の条件で「配列の大きさは最大で100」ですが、これではあまり違いはわかりません。
しかし連続するk個の和で最大のものを求める場合で、最初の配列が長く、しかもkの値が大きいとどうなるでしょうか？ ここからは管理人の自由研究です。
巨大な配列
まず乱数を発生させるメソッドをつくります。乱数だと生成される値で計算にかかる時間に差ができてしまうかもしれないので0～9までの値しか生成されないようにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
using System; class Program { static int[] GetRandomNums() { Random random = new Random(); int count = 8 * 1000 * 1000; // 800万 int[] vs = new int[count]; for (int i = 0; i < count; i++) vs[i] = random.Next(10); return vs; } } |
長く連続するk個の数の和
比較のためにふたつのメソッドを作成します。Test1は累積和を利用して連続するk個の数の和を取得し、Test2は普通の方法で連続するk個の数の和を取得します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
class Program { static void Test1(int k) { int[] vs = GetRandomNums(); System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); sw.Start(); // 累積和を利用して連続するk個の数の和を取得する int[] sn = new int[vs.Length]; for (int i = 0; i < vs.Length; i++) { if (i == 0) sn[i] = vs[0]; else sn[i] = sn[i - 1] + vs[i]; } int max = sn[k - 1]; for (int i = k; i < sn.Length; i++) { if (max < sn[i] - sn[i - k]) max = sn[i] - sn[i - k]; } Console.WriteLine(max); sw.Stop(); Console.WriteLine("実行時間：" + sw.ElapsedMilliseconds); } static void Test2(int k) { int[] vs = GetRandomNums(); System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); sw.Start(); // 連続する3つの数の和をなにも工夫しないで取得する int max = 0; for (int i = 0; i + (k - 1) < vs.Length; i++) { int sum = 0; for (int m = 0; m < k; m++) { sum += vs[i + m]; } if (max < sum) max = sum; } Console.WriteLine(max); sw.Stop(); Console.WriteLine("実行時間：" + sw.ElapsedMilliseconds); } } |
結果はいかに？
これで実行時間を比較します。どのようなPCを使うかで結果はかわりますが、ここまで極端なことをすると大きな差になりました。累積和を使えば0.1秒程度で終わりますが、使わないと6秒もかかります。約60倍の違いです。
|
1 2 3 4 5 6 7 8 9 |
class Program { static void Main() { // Test1(256); 実行時間は 103 ms だった // Test2(256); 実行時間は 6000ms だった（約 60倍 違う） return; } } |
何度も計算を繰り返す場合は累積和を利用したほうが効率よく結果を取得することができます。
