竹内関数をメモ化で高速化する工程 (Python には負けたくない)

# はじめに

Ruby で竹内関数をメモ化によって、高速にしようとあれこれやります。

## 竹内関数とは

[これ](https://ja.m.wikipedia.org/wiki/竹内関数)です。Ruby で書くとこんな感じです。

```ruby:Ruby
def tarai(x, y, z)
  return y if x <= y
  tarai(
    tarai(x - 1, y, z),
    tarai(y - 1, z, x),
    tarai(z - 1, x, y)
  )
end
```

引数をたらい回しにして、再帰しまくることにより、重い処理になっています。

迂闊に、

```ruby
tarai(30, 15, 0)
```

とかすると、後悔します。

## メモ化とは

竹内関数が遅いのは、引数をたらい回しにして再帰的に関数を実行することで、引数が同じなのに、何度もなんども同じ計算をしなければならないためです。

そこで、ある引数の組合せで計算を一度してしまえば、その答えをメモしておいて、もう一度同じ引数の計算をしなければならなくなった時に、実際に計算するのでなく、メモに記録した答えを返すようにすることで、速く答えを出す、というものです。

## で、何をしようというの？

Fibonacci 数を求める `fibo(n)` のように引数がひとつの時には、特に問題はありません。

```ruby:Ruby
def make_fibo
  cache = {}
  fibo = lambda do |n|
    return n if n < 2
    cache[n] ||= fibo.call(n - 2) + fibo.call(n - 1)
  end
end

fibo = make_fibo
fibo.call(100)
```
すればＯＫです。
ここでは、計算結果を、引数をキーにした Hash オブジェクト `cache` にメモしています。ちなみに、`cache` をグローバル変数にしたくないので、`lambda` を使ってクロージャを作っています。

`def ... end` で囲まれた空間は、局所変数の独立した 名前空間 を作るので、`def` で作ったメソッドは外側の局所変数をキャプチャーできず、クロージャにはなりません。

その代わり、`lambda` 等を使ってクロージャを作る時には、`def ... end` の中は、局所変数に関してはクリーンルームになるので、クロージャを返すメソッドを作った上で、クロージャを作るのがオススメのはずです。多分。

話が飛んでしまいましたが、Fibonacci の場合と違い、竹内関数の場合、引数が３つあります。これをどう Hash オブジェクトに登録するかです。

# Python ならどうするか

Python なら、当然引数を tuple にして、dict オブジェクトに登録するはずです。

まずは、クロージャを使って、

```python:Python
def make_tarai:
    cache = {}
    def tarai(x, y, z):
        if x <= y:
            return y
        key = (x, y, z)
        val = cache.get(key)
        if val is not None:
            return val
        val = tarai(
            tarai(x-1, y, z),
            tarai(y-1, z, x),
            tarai(z-1, x, y)
        )
        cache[key] = val
        return val
    return tarai

tarai = make_tarai()
tarai(100, 50, 0)
```

あるいは、Python のデフォルト引数は関数を定義した時に一度だけ評価されるので、

```python:Python
def tarai(x, y, z, cache={}):
    if x <= y:
        return y
    key = x, y, z
    val = cache.get(key)
    if val is not None:
        return val
    val = tarai(
        tarai(x-1, y, z, cache),
        tarai(y-1, z, x, cache),
        tarai(z-1, x, y, cache),
        cache
    )
    cache[key] = val
    return val

tarai(100, 50, 0)
```

でもＯＫでしょう。`tarai` 関数を何度実行しても、常に同じ `dict` オブジェクトが使われるので、一度計算結果をメモしてしまえば、次に `tarai` を実行した時にもそのメモが使えます。

手元で計算すると、`tarai(100, 50, 0)` で約0.03 秒程度です。

# Ruby で同じようなことをすると

Rubyの場合、デフォルト引数はメソッドを実行するたびに評価されるので、Python と違い、メソッドを実行するたびに一からメモを取り直すことになってしまいます。

どちらがいいのか私にはよく分かりません。Python が変わっているような印象ですが、どちらが勝ちで、どちらが負けという話でないことは間違いなさそうです。

そういうわけで、Ruby の場所、クロージャでいきます。
Ruby には tuple がないので、配列でやるしかありません。

```ruby:Ruby
def make_tarai
  cache = {}
  tarai = lambda do |x, y, z|
    return y if x <= y
    cache[[x, y, z]] ||= tarai.call(
      tarai.call(x - 1, y, z),
      tarai.call(y - 1, z, x),
      tarai.call(z - 1, x, y)
    )
  end
end

tarai = make_tarai
tarai.call(100, 50, 0)
```

できるにはできましたが、Python に比べると圧倒的に遅いです。手元で計算すると、0.09 秒前後かかってしまいました。完敗です。

```ruby:Ruby
def time
  start = Time.now
  result = yield
  diff = Time.now - start
  puts "Elapsed time: #{diff} secs"
  p result
end

time { tarai.call(100, 50, 0) }
```

で時間を計算しましたが、以下略。

Python の tuple は見た目が同じなら同じオブジェクトです（少なくとも中身がintの場合）。なので高速に dict のキーを比較することができます。

それに対し、Ruby の配列は見た目が同じでも別のオブジェクトになりうるので、キーの比較に時間がかかってしまうのが大きな原因だと思います。

ここからが知恵の出しどころです。

# 計算結果を多重 Hash に登録する

配列をキーにするから遅いのなら、メモを多重 Hash にして、Integer である、個々の`x`, `y`, `z` をキーにして、計算結果をメモすることにします。

戦略的には、まず、引数 `x` のための `cache_x = {}` を用意します。
そして、`cache_x[x]` は引数 `y` のための Hash オブジェクト `cache_y` を返して欲しいのですが、引数 `x` が初見であれば `nil` が返ってきます。
そこで、`cache_y = cache_x[x] ||= {}` とすることで、`x` が初見の場合には、新たな Hash オブジェクトを `cache_[x]` に登録した上で、変数 `cache_y` に代入することができます。

そうすると、こんな感じになります。

```ruby:Ruby
def make_tarai
  cache_x = {}
  tarai = lambda do |x, y, z|
    return y if x <= y
    cache_y = cache_x[x] ||= {}
    cache_z = cache_y[y] ||= {}
    cache_z[z] ||= tarai.call(
      tarai.call(x - 1, y, z),
      tarai.call(y - 1, z, x),
      tarai.call(z - 1, x, y)
    )
  end
end

tarai = make_tarai
tarai.call(100, 50, 0)
```

0.012 秒前後です。
やりました。Python に勝ちました。圧勝です。

ちなみに、Python でこの方法を使うと少し遅くなってしまいました。恐るべし、Python の tuple 。

しかし、Ruby が勝ったとはいえ、

```ruby:Ruby
    cache_y = cache_x[x] ||= {}
    cache_z = cache_y[y] ||= {}
    cache_z[z] ||= tarai.call(...
```
の部分がまだだるいです。どうせなら `cache[x][y][z] ||= tarai.call( ...` としたいです。

# Hash のデフォルト値を使う

Ruby の場合、

```ruby:Ruby
cache = Hash.new { |hash, key| hash[key] = {} }
```
とすることで、未登録のキーに出くわしたとき、新たな Hash オブジェクトを作って、そのキーに登録するような Hash オブジェクトを作ることができます。
これを多重にすればいいわけです。

```ruby:Ruby
def make_tarai
  cache = Hash.new do |hash, key|
    hash[key] = Hash.new do |hash, key|
      hash[key] = {}
    end
  end

  tarai = lambda do |x, y, z|
    return y if x <= y
    cache[x][y][z] = tarai.call(
      tarai.call(x - 1, y, z),
      tarai.call(y - 1, z, x),
      tarai.call(z - 1, x, y)
    )
  end
end

tarai = make_tarai
tarai.call(100, 50, 0)
```

これでＯＫです。
とはいえ、この `cache` の定義もだるいです。何とかスマートにしたいものです。

そこで、`cache` の右辺をよく見ると、ラスボス的な `{}` を `Hash.new { |hash, key| hash[key] = ... }` でラップしていけば良さそうだと分かります。メタプログラミングで何とかしましょう。

# メタプログラミング登場

方針としては、何重にもなった `Hash.new {}` の文字列を作って、`eval` することにします。

引数の数が３つの場合、`{}` を２回 `Hash.new {}` でラップすればいいから、メモ化する際の引数の数を `arity` とすると、

```ruby:Ruby
def make_cache(arity)
  seed = "{}"
  (arity - 1).times do
    seed = "Hash.new { |hash, key| hash[key] = #{seed} }"
  end
  eval(seed)
end
```

この `make_cache` があれば、簡単に多重 Hash を作ることができます。

```ruby:Ruby
def make_cache(arity)
  seed = "{}"
  (arity - 1).times do
    seed = "Hash.new { |hash, key| hash[key] = #{seed} }"
  end
  eval(seed)
end

def make_tarai
  cache = make_cache(3)
  tarai = lambda do |x, y, z|
    return y if x <= y
    cache[x][y][z] ||= tarai.call(
      tarai.call(x - 1, y, z),
      tarai.call(y - 1, z, x),
      tarai.call(z - 1, x, y)
    )
  end
end

tarai = make_tarai
tarai.call(100, 50, 0)
```

かなりいい感じになりました。でも、もっと高速を目指したいです。

いろんな事情があって、Proc オブジェクトはメソッドより遅いと聞きます。そこで、Proc オブジェクトではなく、メソッドでクロージャを作ってみます。

# メソッドでクロージャを作る

すでに述べたように、`def` でクロージャは作れません。そこで、`def` を使わずにメソッドを作ることにします。

`define_method` の登場です。

```ruby:Ruby
def make_cache(arity)
  seed = "{}"
  (arity - 1).times do
    seed = "Hash.new { |hash, key| hash[key] = #{seed} }"
  end
  eval(seed)
end

def make_tarai
  cache = make_cache(3)
  define_method(:tarai) do |x, y, z|
    return y if x <= y
    cache[x][y][z] ||= tarai(
      tarai(x - 1, y, z),
      tarai(y - 1, z, x),
      tarai(z - 1, x, y)
    )
  end
  private :tarai
end

make_tarai
tarai(100, 50, 0)
```

トップレベルで `make_tarai` を定義すると、定義式の中の `self` は `main` になります。`define_method` は Module クラスのメソッドなので、一般的には `module ... end` か `class ... end` の中でしか使えないのですが、`main` には同名のシングルトン・メソッドが定義されていて、実行すると、Object クラスにメソッドが登録されます。

ここでは、トップクラスでメソッドを定義したときのように、private にしました。

ただ、メソッドにしてもほとんど速度は変わりません。Proc にしろ、メソッドにしろ、環境を背負っている分、遅いのでしょうか。

そこで、この辺りでクロージャに見切りをつけ、`cache` をインスタンス変数で持つ方法を試してみます。

# メモをインスタンス変数に格納する

```ruby:Ruby
def make_cache(arity)
  seed = "{}"
  (arity - 1).times do
    seed = "Hash.new { |hash, key| hash[key] = #{seed} }"
  end
  eval(seed)
end

class Tarai
  def initialize
    @cache = make_cache(3)
  end

  def call(x, y, z)
    return y if x <= y
    @cache[x][y][z] ||= call(
      call(x - 1, y, z),
      call(y - 1, z, x),
      call(z - 1, x, y)
    )
  end
end

tarai = Tarai.new
tarai.call(100, 50, 0)
```

ついに、0.007 秒の世界に突入しました。
ぶっちぎりの速さです。

関数型言語に惑わされてなのか、メモ化というとすぐにクロージャだと思い込んでいましたが、Purely Object-Oriented Programming Language である Ruby の場合、素直にオブジェクトを使えばよかったんですね。

# まとめ

Ruby でメソッドをメモ化する時には、クロージャではなく、普通にインスタンスを作って、インスタンス変数にメモを格納する。

引数が複数あるときは、配列にして Hash オブジェクトのキーにするのではなく、引数の数だけ多重 Hash にする。