はじめに
今回は累積和を実装してみようという記事になります!
そもそも累積和をどこに使う必要があるのかというとこんな時です。
適切な前処理をしておくことで、配列上の区間の総和を求めるクエリを爆速で処理できるようになる手法
軽く累積和の仕組みについて調べながら実際にC#で実装してみようと思います。
累積和とは
どのように前処理をして高速で区間内の総和を求めるかについて説明していきたいと思います。
まず前処理はn個の要素を持つ配列a[]
に対して以下のような配列を作ることことを指します。
s[0] = 0 s[1] = a[0] s[2] = a[0] + a[1] ・ ・ s[n] = a[0] + a[1] + ... + a[n-1]
添字が結構ややこしいですが、そこは我慢するしかありません。
この下準備をしておくことで区間を以下のように計算することができます。
1以上3未満の区間の最大値 s[3] - s[1] (= (a[0] + a[1] + a[2]) - (a[0]))
こうすることで前処理に計算量かかりますが、区間の最大値は計算量
で取り出すことができます。
実装してみる
/// <summary> /// 累積和 /// </summary> public class CumulativeSum { public long[] Array { get; } public CumulativeSum(IReadOnlyList<int> array) : this(array.Select(t => (long)t).ToArray()) { } public CumulativeSum(IReadOnlyList<long> array) { var length = array.Count; Array = new long[length + 1]; for (int i = 0; i < length; i++) { Array[i + 1] = array[i] + Array[i]; } } /// <summary> /// left以上right未満の総和 /// </summary> /// <param name="left">以上</param> /// <param name="right">未満</param> public long GetSum(int left, int right) { if (left >= right) return 0; return Array[right] - Array[left]; } }
本当はジェネリック を使いたかったのですが、どんな制約をつけようとも+
といった演算はできないんですね。
普通にできると思っていてビックリしてしまいました。
dynamic
も検討しましたが処理速度が遅くなってしまうのは致命傷なので、結局long型
に限定してしまいました。
小数版
ただlong型
にしてしまったせいで少数の計算ができなくなってしまったので、小数版も書きました。
なんかうまく一緒にできる方法を見つけたら書き直したいと思います。
/// <summary> /// 累積和 /// </summary> public class CumulativeSum { public double[] Array { get; } public CumulativeSum(IReadOnlyList<float> array) : this(array.Select(t => (double)t).ToArray()) { } public CumulativeSum(IReadOnlyList<double> array) { var length = array.Count; Array = new double[length + 1]; for (int i = 0; i < length; i++) { Array[i + 1] = array[i] + Array[i]; } } /// <summary> /// left以上right未満の総和 /// </summary> /// <param name="left">以上</param> /// <param name="right">未満</param> public double GetSum(int left, int right) { if (left >= right) return 0; return Array[right] - Array[left]; } }
使い方
使い方はこんな感じ。
class Program { static void Main(string[] args) { // 1 ~ 10を格納した配列 var array = Enumerable.Range(1, 10).ToArray(); var cSum = new CumulativeSum(array); // インデックスが5以上7未満の和を求める (6, 7) var sum = cSum.GetSum(5, 7); Console.WriteLine(sum); // 13 } }
さいごに
やっぱり添字関係が結構こんがらがってしまいがちですが、簡単な仕組みの割には結構速度を出してくれます。
またいままでIReadOnlyList
みたいなインターフェイスを使うと処理速度が結構落ちるのではないかと思っていましたが、実際に時間をしらべてみたらそこまで変化はありませんでした。
コンストラクタのみなのでそうなったのかもしれませんが、あまり気にしなくも良かったのかもしれません。
とりあえず今回はこれくらいで。
ではまた。