これはなに？

つい先日Linqをバキバキ書いていたらハマったので覚書き。

遅延評価は良いのだが、組み合わせが増えるケースで遅延評価を効かせていると効率の良い計算（枝刈り）が行われず遅くなってしまうよ、という話。

とりあえず.Net Framework 4.8（とある事情で使っている）で試してみたけど.NETでも同じなんじゃないかなぁ……。

プロダクトコード

public class LazyLinq
{
    public static List<(int num1, List<int>)> LinqChain(List<int> list1, List<int> list2)
    {
        IEnumerable<LongTimeConstructor> enumerable =
            list2.Select(num => new LongTimeConstructor(num));

        List<(int num1, List<int>)> result = list1.Select(num1 => (
            num1,
            enumerable.Where(num2 => num2.Num == num1).Select(num2 => num2.Num * num1).ToList()
        )).ToList();

        return result;
    }

    public static List<(int num1, List<int>)> LinqChainFast(List<int> list1, List<int> list2)
    {
        List<LongTimeConstructor> enumerable =
            list2.Select(num => new LongTimeConstructor(num)).ToList();

        List<(int num1, List<int>)> result = list1.Select(num1 => (
            num1,
            enumerable.Where(num2 => num2.Num == num1).Select(num2 => num2.Num * num1).ToList()
        )).ToList();

        return result;
    }
}

public class LongTimeConstructor
{
    public int Num { get; set; }

    public LongTimeConstructor(int num)
    {
        // await Task.Delay(1000); はコンストラクタ内では使えない？
        System.Threading.Thread.Sleep(100);
        Num = num;
    }
}

テストコード

[TestMethod()]
public void LinqChainTest()
{
    List<int> lis1 = Enumerable.Range(0, 10).ToList();
    List<int> lis2 = Enumerable.Range(0, 10).ToList();

    Stopwatch stopWatch = new Stopwatch();
    stopWatch.Start();
    LazyLinq.LinqChain(lis1, lis2);
    stopWatch.Stop();

    // Green
    Assert.IsTrue(stopWatch.Elapsed.TotalSeconds < 12.0);
    // Red
    Assert.IsTrue(stopWatch.Elapsed.TotalSeconds < 2.0);
}

[TestMethod()]
public void LinqChainFastTest()
{
    List<int> lis1 = Enumerable.Range(0, 10).ToList();
    List<int> lis2 = Enumerable.Range(0, 10).ToList();

    Stopwatch stopWatch = new Stopwatch();
    stopWatch.Start();
    LazyLinq.LinqChainFast(lis1, lis2);
    stopWatch.Stop();

    // Green
    Assert.IsTrue(stopWatch.Elapsed.TotalSeconds < 12.0);
    // Green
    Assert.IsTrue(stopWatch.Elapsed.TotalSeconds < 2.0);
}

結果

解説

最初のLinqChain関数は、関数内でLinqの結果をIEnumerableで持ちまわっている。IEnumerableは通常は遅延評価を行うので計算効率が良く高速のハズである。しかし、 list2.Select(num => new LongTimeConstructor(num)); のように内部で100ミリ秒を要する重い処理（例えば何らかのAPIから値を取得するとか……）などを行い、これをIEnumerable型の結果としてしまうと、計算が実行されずに保留されてしまう。

次に結果を計算する処理内で、 enumerable.Where(num2 => num2.Num == num1).Select(num2 => num2.Num * num1).ToList() とするとそこで初めて保留した処理も含めて「評価」されるわけだが、どうもこの時全組み合わせが計算されてしまうらしい。つまり new LongTimeConstructor(num) を10回計算した後、 num2 => num2.Num == num1 と num2 => num2.Num * num1 を高々100回ずつ計算することを期待したのに、new LongTimeConstructor(num) まで100回計算してしまうわけだ。

それでめでたく System.Threading.Thread.Sleep(100); が100回呼ばれて10秒以上かかってしまうわけ。

これを回避するには、遅延評価をしない、つまり計算を1回確定させてしまえばよく、LinqChainFastTest関数では list2.Select(num => new LongTimeConstructor(num)); の結果を ToList() して1度ここまでで評価を確定させている。これなら期待通り10回実行されるだけで済むわけだ。

かように、組み合わせ爆発が起きそうな場合は注意が必要。

……Scheme/Gaucheだとこういうことにはあまり遭遇した記憶が無いんだけど、忘れてるだけかな……。いずれにせよ遅延評価の計算過程には気を付けておく必要があり、IEnumerableの濫用は控えた方がいいかもね、という話。

コードリポジトリ

https://github.com/aki426/LazyLinqChainTest

追記

こんなときはMemoize（メモ化）だ。

プロダクトコード

ちょっとしたメモ化を施した。これがC#のベスプラかどうかは知らないので、もっと良い書き方があるかもしれない。

public class MemoizedConstructor
{
    public static Dictionary<int, MemoizedConstructor> memo =
        new Dictionary<int, MemoizedConstructor>();

    public static MemoizedConstructor Create(int num)
    {
        if (memo.ContainsKey(num))
        {
            return memo[num];
        }
        else
        {
            MemoizedConstructor temp = new MemoizedConstructor(num);
            memo.Add(num, temp);
            return temp;
        }
    }

    public int Num { get; set; }

    private MemoizedConstructor(int num)
    {
        // await Task.Delay(1000); はコンストラクタ内では使えない？
        System.Threading.Thread.Sleep(100);
        Num = num;
    }
}

テストコード

public static List<(int num1, List<int>)> LinqChainMemoized(List<int> list1, List<int> list2)
{
    IEnumerable<MemoizedConstructor> enumerable =
        list2.Select(num => MemoizedConstructor.Create(num));

    List<(int num1, List<int>)> result = list1.Select(num1 => (
        num1,
        enumerable.Where(num2 => num2.Num == num1).Select(num2 => num2.Num * num1).ToList()
    )).ToList();

    return result;
}

[TestMethod()]
public void LinqChainMemoized()
{
    List<int> lis1 = Enumerable.Range(0, 10).ToList();
    List<int> lis2 = Enumerable.Range(0, 10).ToList();

    Stopwatch stopWatch = new Stopwatch();
    stopWatch.Start();
    LazyLinq.LinqChainMemoized(lis1, lis2);
    stopWatch.Stop();

    // Green
    Assert.IsTrue(stopWatch.Elapsed.TotalSeconds < 12.0);
    // Green
    Assert.IsTrue(stopWatch.Elapsed.TotalSeconds < 2.0);
}

結果

まあ当たり前の結果と言えば当たり前の結果。枝刈りするか、メモ化するか、要はムダな計算を省く方法なわけです。

どちらかというと遅延評価を自覚的に使って、枝刈りした方が簡単とは思いますが、エンジニアの認知負荷が上がるのでしっかり設計するならFactoryパターンでメモ化しちゃった方が良いかもしれません（メモリ空間消費とのトレードオフがあることは言うまでもないですが）。