たらい回し関数の調査
たらい回し関数は変数を使わない例には使えそうにないですが、調査を継続します。「wikipedia:竹内関数」に書かれている高速化をやってみます。C# で書いた以下のプログラムについて考えます。
public static string Test() { int count = 0; int tarai(int x, int y, int z) { count++; if (x <= y) { return y; } else { return tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)); } } return $"{tarai(12, 6, 0)}, count = {count}"; }
普通に を実行すると結果は以下のようになります。
12, count = 12604861
呼ばれている回数は 12604861 回となります。
遅延評価
のときは を計算する必要はないので、 をクロージャー化すると呼び出し回数を減らすことができます。
public static string Test() { int count = 0; int tarai(int x, int y, Func<int> zf) { count++; if (x <= y) { return y; } else { return tarai(tarai(x - 1, y, zf), tarai(y - 1, zf(), () => x), () => tarai(zf() - 1, x, () => y)); } } return $"{tarai(12, 6, () => 0)}, count = {count}"; }
結果
12, count = 109
呼び出し回数は 109 回になりました。
メモ化
Dictionary に の組を保存し、同じ組に対しては一度しか計算をしないようにします。
public static string Test() { Dictionary<(int, int, int), int> dic = new Dictionary<(int, int, int), int>(); int count = 0; int tarai(int x, int y, int z) { count++; if (x <= y) { return y; } else { if (dic.ContainsKey((x, y, z))) { return dic[(x, y, z)]; } else { int val = tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)); dic[(x, y, z)] = val; return val; } } } return $"{tarai(12, 6, 0)}, count = {count}"; }
結果
12, count = 449
呼び出し回数は 449 回になりました。