すもぎのめも

いろいろあったことをメモしています

シーケンスから要素を取得し合計値が指定した条件になるまで一覧を作成する拡張メソッド

.NET

いったい何を言いたいのかわからないタイトルになってしまいました。日本語難しい。 期待する結果のイメージは以下の通り。

[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 に放流

したところ、2名の方から反応をいただきました。

助言によって完成したのが冒頭のコードになります。見るからにパフォーマンスが向上していますし、見通しもよくなってますね。パフォーマンスと可読性が同時に上がるとは…… (元のコードが悪い) さて、どのくらいパフォーマンスが向上したのか計測してみましょう。

パフォーマンス計測にあたり、手軽なマイクロベンチマークを使用することにしました。

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)

C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION)

  • 作者: Sasha Goldshtein,Dima Zurbalev,Ido Flatow,サシャ・ゴルドシュタイン,ディマ・ズルバレフ,イド・フラトー,株式会社プロシステムエルオーシー
  • 出版社/メーカー: 翔泳社
  • 発売日: 2013/07/23
  • メディア: 大型本
  • この商品を含むブログ (4件) を見る

最後に、レビューしていただいたお二方にお礼申し上げます。しかしながら、Sum に関しては少し考えればわかるものでした。恥ずかしいコードを晒してしまった。selector のコストは考えたことがなかったので勉強になりました。