C#のLinqによるリスト操作で、評価を遅延させたままメモ化したい

Question

実現したいこと

C#のLinqによるリスト操作において、参照するまでは評価されず、一度評価したものについては二度目の評価を行わせないようにしたいです。

例えば次のようなコードにおいて、メモ化されていればMapメソッドの実行回数は10回となりますが、メモ化されていないがために15回実行されてしまいます。

using System;
using System.Linq;
using System.Collections.Generic;

public class Sample {
    
    private static int _counter = 0;
    
    public static void Main() {
        var xs = GetList();
        var mapped = xs.Select(Map);
        Console.WriteLine(mapped.Take(5).Count());
        foreach (var x in mapped.Take(10)) {
            Console.WriteLine(x);
        }
        Console.WriteLine($"about counter: expected=10, actual={_counter}"); //=> about counter: expected=10, actual=15
    }
    
    private static IEnumerable<int> GetList() {
        var n = 0;
        while (true) {
            yield return n++;
        }
    }
    
    private static int Map(int x) {
        _counter++;
        return x;
    }
}

これを、遅延評価的な挙動を維持したまま適切にメモ化するにはどうすればよいでしょうか？

Answer 1

求めている答えかわかりませんが、
Ixライブラリを使って、11行目を書き換えます。

//var mapped = xs.Select(Map);
var mapped = xs.Select(Map).Memoize();

この例ではvar mapped = xs.Select(Map).Take(10).ToArray(); で済ませることが多いとは思いますが・・。

追記：Ix.Memoize()のソースを貼っておきます。
https://github.com/dotnet/reactive/blob/main/Ix.NET/Source/System.Interactive/System/Linq/Operators/Memoize.cs

Comments

[noff]

ご回答ありがとうございます、やはり実装する人が区切りの良いタイミングで明示的にメモ化するか、利用側が参照前に使う範囲をあらかじめ評価してしまうしか方法がなさそうですね。

ありがとうございました。

[hqf00342]

Shunlyさんの回答コードもそうだと思いますが、このMemoize()は遅延評価ですので
やりたいことはできているはずですよ。
（最初のTake(5)の段階で5回、最後の結果は10回になっているはず）

質問のコードのようなケースでは即時評価が最善ですが、
ネットワーク越しにデータ取得→Webページに表示、などご質問のニーズは多く、
実践では皆さんいろんな工夫で実装されていると思います。

[noff]

hqf00342 さん

コメントありがとうございます。
メモ化ですので、一般には一度実行されるまでは評価されず、実行したらキャッシュされて二度目以降は評価が行われないという認識ですので、遅延評価的な挙動であると理解しています。
また追記いただいているリンクからソースを読んでも、評価済みのインデックスまではバッファから、評価されていないインデックスへ差し掛かると評価してバッファに積みながら値を返すようなイテレータを生成することが読み取れます。

ただ、リスト操作の途中で操作対象のリストを評価しなければならない場合（例えばシーケンス内の最大・最小値をintで表現できる数値の最大・最小値へnormalizeする処理など）、次のソースのようにその手前で明示的にMemoizeを呼ばなければならないのが微妙だなと思っています。

（ゼロ除算や負数でのオーバーフローが起こりうるコードですが、簡単のためにそこは無視してください）
```cs
IEnumerable<int> Normalize(IEnumerable<int> xs) {
var memoized = xs.Memoize(); // Max で一度評価されるためその前にメモ化しなければならない
var peek = memoized.Max();
return memoized.Select(x => (int)((long)x * int.MaxValue / peek));
}
```

そこで次のような書き方で、都度メモ化のメソッドを呼ばなくても自動でメモ化できるようなライブラリはないかと思いましたが、いただいたコメントから見てもなさそうであると認識したところでした。

```cs
interface IFilter {
IEnumerable<int> Apply(IEnumerable<int> xs);
}
class NormalizeFilter : IFilter
{
public IEnumerable<int> Apply(IEnumerable<int> xs) =>
xs.Select(x => (int)((long)x * int.MaxValue / xs.Max()));
}
class ComprssFilter : IFilter { ... }
class EqualizeFilter : IFilter { ... }

class FilterApplier {
IEnumerable<int> Apply(IEnumerable<IFilter> filters, IEnumerable<int> rawData) =>
filters.Aggregate(rawData.Memoizable(), (f, d) => f(d));
}
```

ですので MemoizableEnumerable のようなクラスを作り、このように記述できるようなライブラリを作ろうと思います。

なお、実装側と利用側といった表現は言葉足らずでした、次のような意味で使っています。
**実装側**: リストの操作そのものが主目的となる処理
**利用側**: 操作されたリストを参照して別の目的に利用することが主目的となる処理

ですので、それぞれ次のようなソースになります。

<u>実装側で明示的にメモ化</u>
```cs
public static void Main() {
var xs = GetList();
// var mapped = xs.Select(Map);
var mapped = xs.Select(Map).Memoize(); // 実装側で明示的にメモ化
Console.WriteLine(mappedArray.Take(5).Count());
foreach (var x in mappedArray.Take(10)) {
Console.WriteLine(x);
}
Console.WriteLine($"about counter: expected=10, actual={_counter}"); //=> about counter: expected=10, actual=15
}
```

<u>利用側であらかじめ評価</u>
```cs
public static void Main() {
var xs = GetList();
var mapped = xs.Select(Map);

var mappedArray = mapped.Take(10).ToArray(); // 利用側であらかじめ評価
Console.WriteLine(mappedArray.Take(5).Count());
foreach (var x in mappedArray.Take(10)) {
Console.WriteLine(x);
}
Console.WriteLine($"about counter: expected=10, actual={_counter}"); //=> about counter: expected=10, actual=15
}
```

追記：
コメントではMarkdownがレンダリングされないんですね…
読みづらくてすみません。

[hqf00342]

書いていただいた汎用度が高いメソッド内でMemoize()を呼び出すのは使い方としては想定していないでしょうね。その場合はIEnumerable<>を引数に取るのではなくIBuffer<>（＝Memoizeされた列挙）を受けるメソッドにするとは思います。
自分好みのライブラリを作るのは（車輪の再発明かもしれませんが）個人的には好きでC#の言語verupのたびによくやってますね（笑）。頑張ってください。

Answer 2

結果をDictionaryに記憶しておくユーティリティ関数を作るとかでしょうか。

var mapped = xs.Select(Memoize<int, int>(Map));

private static Func<T, R> Memoize<T, R>(Func<T, R> generator) where T : notnull
{
    var cache = new Dictionary<T, R>();
    return (key) =>
    {
        if (cache.TryGetValue(key, out R? value))
        {
            return value;
        }
        value = generator(key);
        cache.Add(key, value);
        return value;
    };
}

Comments

[noff]

ご回答ありがとうございます。
やはり、区切りの良いタイミングで明示的にメモ化させるしかなさそうですね。