Amosapientiam

備忘録

【C#】メモ化再帰の抽象化

C#を真面目に勉強しようと思い、kekyoさんの

Final LINQ Extensions

を読んでしょっぱなから衝撃を受けた。 C#ってこんなに簡単に無限列が書けるんだ!

イテレータと無限列

たとえば0の無限列のイテレータは以下の通り。

   public static IEnumerable<int> Infinity() {
        while(true) yield return 0;
    }

以下はInfinityを用いて0を100回出力するコード。

   public static void Main (string[] args) {
        Console.WriteLine(string.Join("\n", Infinity().Take(100)));
    }

Fibonacci数列なら以下のように書ける。

   public static IEnumerable<ulong> Fib(){
        yield return 0;
        yield return 1;
        foreach (var k in Fib().Skip(1).Zip(Fib(), (m, n) => m + n)) {
            yield return k; 
        }
    }

    public static void Main (string[] args) {
        foreach (var n in Fib().Take(40)) {
            Console.WriteLine(n);
        }
    }

書ける。が、上記のコードは再帰を使っており遅い。そこで、メモ化して線形時間で計算できるようにする。

   public static IEnumerable<ulong> MemoFib(){
        ulong predpred = 0;
        ulong pred = 1;
        yield return predpred;
        yield return pred;
        while (true) {
            ulong current = predpred + pred;
            predpred = pred;
            pred = current;
            yield return current;
        }
    }

無事に書けた。が、メモ化により状態管理のコードが混ざったため、先ほどのfib実装が宣言的に書けているのに比べると手続き的だ。 また、メモ化自体は様々な無限列で必要になりうる。そこで、メモ化の仕組みと再帰的な数列生成の部分を切り分けたい。

メモ化

というわけで下のように切り分けた。

   public static IEnumerable<T> memoize<T>(Func<Func<int, T>, int, T> generator){
        Dictionary<int, T> memo = new Dictionary<int, T>();
        T accessor (int n){
            if (!memo.ContainsKey(n)) memo[n] = generator(accessor, n);
            return memo[n];
        };
        int i = 0;
        while(true) yield return accessor(i++);
    }

    public static ulong FibFactory (Func<int, ulong>accessor,int i){
        switch (i) {
        case 0:
        case 1:
            return (ulong)i;
        default:
            return accessor(i - 2) + accessor(i - 1);
        };
    }
        
    public static void Main (string[] args) {
            foreach (var n in memoize<ulong> (FibFactory).Take(80)) {
            Console.WriteLine (n);
        }
    }

memoize内部のaccessor関数はメモテーブルの読み出しをラップし、すでに値が計算されていればテーブルの値を使い、そうでなければgeneratorを用い値を計算する。 generatorはaccessorとindexを受け取り、数列のindex番目の値を計算する。