シーケンスから要素を取得し合計値が指定した条件になるまで一覧を作成する拡張メソッド
いったい何を言いたいのかわからないタイトルになってしまいました。日本語難しい。 期待する結果のイメージは以下の通り。
[TestMethod] public void 合計値が条件に一致したところで分割される() { var source = "The quick brown fox jumps over the lazy dog".Split(' '); var expected = new[] { ToReadOnlyList(new[] { "The", "quick", "brown" }), ToReadOnlyList(new[] { "fox", "jumps", "over", "the" }), ToReadOnlyList(new[] { "lazy", "dog" }) }; var actual = source.ChunkBySumIf(s => s.Length, sum => sum <= 15); StructuralAssert.AreEqual(expected, actual); }
これを実現するコードがこちら。
public static IEnumerable<IReadOnlyList<T>> ChunkBySumIf<T>(this IEnumerable<T> source, Func<T, double> selector, Func<double, bool> predicate) { if (source == null) throw new ArgumentNullException(nameof(source)); if (selector == null) throw new ArgumentNullException(nameof(selector)); if (predicate == null) throw new ArgumentNullException(nameof(predicate)); using (var enumerator = source.GetEnumerator()) { var values = new List<T>(); var acc = 0.0; while (enumerator.MoveNext()) { var x = selector(enumerator.Current); if (predicate(acc + x)) { values.Add(enumerator.Current); acc += x; } else { yield return values.AsReadOnly(); values = new List<T> { enumerator.Current }; acc = x; } } if (values.Count > 0) { yield return values.AsReadOnly(); } } }
用途はかなり限定的ですが個人的にはとても役立ちました。名前は F# の chunkBySize
関数と Excel の SUMIF
関数が由来です。
ここからはコードが洗練されるまでの道程です。
最初に書いたコードは次のものでした (※元のソースは VB)。
public static IEnumerable<IEnumerable<T>> ChunkBySumIf<T>(this IEnumerable<T> source, Func<T, double> selector, Func<double, bool> predicate) { if (source == null) throw new ArgumentNullException(nameof(source)); if (selector == null) throw new ArgumentNullException(nameof(selector)); if (predicate == null) throw new ArgumentNullException(nameof(predicate)); using (var enumerator = source.GetEnumerator()) { List<T> values = null; while (enumerator.MoveNext()) { values = values ?? new List<T>(); if (predicate(values.Sum(selector) + selector(enumerator.Current))) { values.Add(enumerator.Current); } else { yield return values.Hide(); values = new List<T> { enumerator.Current }; } } if (values?.Count > 0) { yield return values.Hide(); } } } public static IEnumerable<T> Hide<T>(this IEnumerable<T> source) { if (source == null) throw new ArgumentNullException(nameof(source)); using (var enumerator = source.GetEnumerator()) { while (enumerator.MoveNext()) { yield return enumerator.Current; } } }
何となく無駄なことをしている感じがしたので、Twitter に放流
もう少し計算量を減らせないだろうか。どとねとの神様どうかよろしくお願いします https://t.co/kWngDlHeRJ
— SG (@smallgeek) July 4, 2016
したところ、2名の方から反応をいただきました。
@smallgeek これ、ChunkBySumIfの変数valuesがNothingのままであるケースってあるんですか?(values?.Countを見ながら
— 裸のWPF/MVVMを書く男(マン) (@gab_km) July 4, 2016
@smallgeek なるほど、source.GetEnumerator()は空でもIE(T)を返しちゃうか…。
— 裸のWPF/MVVMを書く男(マン) (@gab_km) July 4, 2016
計算量的に、ここ(values.Sum(selector) + selector(enumerator.Current))が気になりますねぇ。
valuesは最初からnewしちゃっていいと思う
— いわた (@wonderful_panda) July 4, 2016
毎回Sum取ってるのは明らかに無駄
HideとかじゃなくてAsEnumerableで十分だと思う(僕ならたぶんそもそも戻す型をIE<IList<T>>にする)
くらいかなあ
https://t.co/EYKXkNKTg2
@smallgeek この実装なら仮にList<T>にキャストして中身を変更されたとしても不正な動作にはならないので、僕はそこはあまり気にしないですね。シグネチャで「IE<T>であることしか保証しない」と表明すれば十分という立場です。人によって異論はあるかと思いますが。
— いわた (@wonderful_panda) July 4, 2016
もう一声。selectorのコストが不明なので呼び出しは1回にしたい。 https://t.co/zeTDVqHDFh
— いわた (@wonderful_panda) July 4, 2016
助言によって完成したのが冒頭のコードになります。見るからにパフォーマンスが向上していますし、見通しもよくなってますね。パフォーマンスと可読性が同時に上がるとは…… (元のコードが悪い) さて、どのくらいパフォーマンスが向上したのか計測してみましょう。
パフォーマンス計測にあたり、手軽なマイクロベンチマークを使用することにしました。
const int OuterIterations = 10; const int InnerIterations = 100000000; var source = new[] { "aaa", "bb", "ccc", "ddddd", "ee", "fff", "gg" }; for (var i = 0; i < OuterIterations; i++) { var sw = Stopwatch.StartNew(); for (var j = 0; j < InnerIterations; j++) { var results = source.ChunkBySumIf(s => s.Length, sum => sum <= 10); // 実体化 foreach (var list in results) { results.Count(); } } sw.Stop(); Console.WriteLine($"Total - {sw.ElapsedMilliseconds}"); }
// 改善前 Total - 574903 Total - 604891 Total - 606887 Total - 586054 Total - 593937 Total - 583028 Total - 587510 Total - 572571 Total - 551103 Total - 531657 // 改善後 Total - 154665 Total - 155299 Total - 162105 Total - 163562 Total - 169325 Total - 180090 Total - 180565 Total - 181161 Total - 180365 Total - 180374
最初の結果は捨て (JIT コンパイラや他のアプリケーションの負荷の影響を考慮)、平均をとって約 3.4 倍の差があることがわかりました。中々にニッチなメソッドですが、速度改善に繋がって満足しています。
マイクロベンチマークについてはこちらを参考にしました。
C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION)
- 作者: Sasha Goldshtein,Dima Zurbalev,Ido Flatow,サシャ・ゴルドシュタイン,ディマ・ズルバレフ,イド・フラトー,株式会社プロシステムエルオーシー
- 出版社/メーカー: 翔泳社
- 発売日: 2013/07/23
- メディア: 大型本
- この商品を含むブログ (4件) を見る
最後に、レビューしていただいたお二方にお礼申し上げます。しかしながら、Sum に関しては少し考えればわかるものでした。恥ずかしいコードを晒してしまった。selector のコストは考えたことがなかったので勉強になりました。