はじめに

自作したLINQメソッドが列挙されすぎていないか調べました。

検証がはかどるのでSystem.Interactive(以下Ix)を事前にインストールしています。

環境

.Net Framework 4.7.1
System.Interactive 3.2.0

列挙回数の確認方法

オレオレLINQメソッドを呼び出す前にローカル変数にアクセスし、列挙回数を記憶させておきます。
このときシーケンスには手を加えずそのまま次に流します。


// 列挙回数記録用変数
int counts = 0;

Enumerable
    .Range(5, 100)
    .Select(x => { counts++; return x; })
    .MyLinqMethod() // オレオレLINQメソッド
    .ToArray();

Console.WriteLine($"列挙回数は {counts} 回です。");

IxのDoメソッドを使うことで同様の処理が短く記述できます。


// 列挙回数記録用変数
int counts = 0;

Enumerable
    .Range(5, 100)
    .Do(x => counts++)
    .MyLinqMethod() // オレオレLINQメソッド
    .ToArray();

Console.WriteLine($"列挙回数は {counts} 回です。");

列挙し過ぎた例

列挙しすぎた場合の例としてオリジナルの集計メソッドMyAggregateを用意しました。
これを先程書いた確認方法を用いて何回列挙されたか調べます。

例1

public static class MyLinq
{
    /// <summary>
    /// シーケンスの現在値と合計値のペアを返します。
    /// </summary>
    public static IEnumerable<(int i, int sum)> MyAggregate(this IEnumerable<int> source)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source));
        }

        IEnumerable<(int i, int sum)> _MyAggregate()
        {
            foreach (var i in source)
            {
                yield return (i, source.Sum());
            }
        }
        
        return _MyAggregate();
    }
}

class Program
{
    static void Main(string[] args)
    {
        int counts = 0;

        Enumerable
            .Range(5, 100)
            .Do(x => counts++)
            .MyAggregate()
            .ToArray();
        
        Console.WriteLine($"列挙回数は {counts} 回です。");
        // 列挙回数は 10100 回です。
    }
}

例1ではEnumerable.Range(5, 100)という5始まり100要素のシーケンスを用いています。要素数が100のためここでの列挙回数も100であることが望ましいのですが、結果は10100という期待と異なる数値になっています。

なぜこのように列挙回数が膨大なもの( $O(n^2)$ )になるのかというとforeach (var i in source)oreach、source.Sum()でそれぞれ列挙が行われているからです。foreachで処理が1回行われるたびにsource.Sum()で列挙が100回行われるため総合計が上記の数になります。

次にforeachを使わない例を示します。

オリジナルのグループ化メソッドMyGroupByを作成し、例1と同様に列挙回数を調べます。

例2

    public static class MyLinq
    {
        /// <summary>
        /// シーケンスの現在の位置から連続した5つの要素を一つのグループにして返す。
        /// </summary>
        public static IEnumerable<IEnumerable<int>> MyGroupBy(this IEnumerable<int> source)
        {
            if (source == null)
            {
                throw new ArgumentNullException(nameof(source));
            }

            IEnumerable<IEnumerable<int>> _MyGroupBy()
            {
                while (source.Any())
                {
                    yield return source.Take(5);
                    source = source.Skip(1);
                }
            }

            return _MyGroupBy();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            int counts = 0;

            Enumerable
                .Range(5, 100)
                .Do(x => counts++)
                .MyGroupBy()
                .SelectMany(x => x) // .Take(5)の列挙を行うため
                .ToArray();

            Console.WriteLine($"列挙回数は {counts} 回です。");
            // 列挙回数は 10590 回です。
        }
    }

実行した結果、こちらも列挙回数100ではなく10590と膨大な数になっています。

この例ではforeachを使わずにsource = source.Skip(1)でシーケンスを進めています。これによりシーケンス呼び出しが再帰的に行われることとなり、列挙回数が膨大になります( $O(n^2)$ )。このSkipメソッドに関してだけでも列挙は5150回発生しています。

それに加えて.Skip(1)が行われるたびに.Take(5)が行われ上記の列挙回数になっています。

対策

1. 自作しない

自作しなければ列挙数が膨大になるようなメソッドは生まれにくくなるはずです。既存のメソッドで代用できそうならそちらを使うようにしましょう。例えば例2のオレオレLINQメソッドはIxのメソッドを利用して以下のように置き換えることができます(インターフェースは若干異なります)。

Enumerable
    .Range(5, 100)
    .Do(x => counts++)
    .Buffer(5, 1) // MyGroupBy() の置き換え
    .SelectMany(x => x)
    .ToArray();

2. キャッシュする

自作メソッドの中でQueueやStackといったコレクションで要素を記憶しておく実装にすることで同じ要素が複数回列挙されることを防ぐことができます。

またメソッドには手を加えずに自作メソッドを呼び出す前にキャッシュを持っておくという手もあります。

Enumerable
    .Range(5, 100)
    .Do(x => counts++)
    .ToArray() // キャッシュ
    .MyGroupBy()
    .SelectMany(x => x)
    .ToArray();

IxのMemoizeメソッドを使うとコードを読んだときにメモ化が行われていることが理解しやすくなります。

Enumerable
    .Range(5, 100)
    .Do(x => counts++)
    .Memoize() // キャッシュ
    .MyGroupBy()
    .SelectMany(x => x)
    .ToArray();

最後に

オレオレLINQメソッドの実装次第で思いがけずシーケンスが複数回列挙されてしまうことを確認しました。

シーケンスが複数回列挙されてしまうことの問題点としては以下が挙げられます。

1回しか列挙されない想定のシーケンスが複数回列挙されることでバグが発生するかもしれないこと
パフォーマンス(メモリ使用量、処理速度)が悪化すること

知らないうちに複数回列挙されている事態にならないよう気をつけましょう。