Rubyistのためのメモ化（Memoization）ガイド：基本の書き方から落とし穴まで

今日は、私が特にお気に入りのパフォーマンス改善テクニックのひとつについてお話しします。この手法は手軽に小さなパフォーマンス向上を積み重ねられます。ただし、ごく稀に——本当にごく稀にですが——アプリケーションを瓦礫の山に変えてしまうこともあります。

その名は「メモ化（memoization）」。いかにも難しそうなコンピュータサイエンス用語ですが、やっていることは非常にシンプルです。メソッドが呼ばれるたびに同じ処理を実行するのではなく、初回の戻り値を変数に保存しておき、2回目以降はその保存された値を使い回すだけです。

擬似コードで書くと次のようになります。

def my_method
  @memo = <work> if @memo is undefined
  return @memo
end

Rubyで書くとこうなります。これは最も堅牢な書き方ですが、やや冗長です。より簡潔な書き方は後ほど紹介します。

class MyClass
  def my_method
    unless defined?(@my_method)
      @my_method = begin 
         # 計算処理、データベースへのクエリなど
         # 時間のかかる処理をここに書きます。
      end
    end
    @my_method
  end
end

上記のコードは3つのことを行っています。

1. @my_method という名前のインスタンス変数が定義されているかどうかを確認する。
2. まだ定義されていなければ、何らかの処理を実行し、その結果を @my_method に保存する。
3. @my_method を返す。

メソッド名とインスタンス変数名がどちらも my_method になっていて混乱しないでください。変数名は何でも構いませんが、メモ化対象のメソッドに合わせて名前を付けるのが慣習となっています。

省略記法による書き方

先ほどのコードにはひとつ問題があります。少し冗長なのです。そのため、実際のコードではほぼ同等の動作をする省略記法の方を目にすることの方が多いでしょう。

class MyClass
  def my_method1
    @my_method1 ||= some_long_calculation
  end

  def my_method2
    @my_method2 ||= begin
      # begin-end ブロックを使えば
      # 複数行のコードも簡単に書けます。
    end
  end
end

どちらもRubyの a ||= b という演算子を使っています。これは a || (a = b) の省略形であり、さらに言えば次のようなコードとほぼ同じ意味です。

# 実際のコードで return をこんな風には使いません。
# 条件式の結果として最終的に `a` に入る値が返されることを
# 初心者向けに表現しているだけです。
if a
  return a
else
  a = b
  return a
end

バグのもとになる落とし穴

よく観察した方ならお気づきかもしれませんが、省略記法ではメモ変数の「存在」をチェックするのではなく、「真偽値（truthiness）」を評価しています。これこそが省略記法の大きな制限のひとつです。nil や false は決してメモ化されないのです。

多くのユースケースではこれは問題になりません。しかし、メモ化を使う際には常に頭の片隅に置いておくべき、厄介な事実のひとつです。

引数を取るメソッドのメモ化

ここまでは単一の値のメモ化だけを扱ってきました。しかし、常に同じ結果を返す関数ばかりではありません。ここで登場するのが、技術面接でおなじみのフィボナッチ数列です。

Rubyでは再帰を使って次のようにフィボナッチ数列を計算できます。

class Fibonacci
  def self.calculate(n)
    return n if n == 0 || n == 1
    calculate(n - 1) + calculate(n - 2)
  end
end

Fibonacci.calculate(10) # => 55

この実装の問題点は非効率なことです。それを証明するために、n の値を出力する print 文を追加してみましょう。

class Fibonacci
  def self.calculate(n)
    print "#{ n } "
    return n if n == 0 || n == 1
    calculate(n - 1) + calculate(n - 2)
  end
end

Fibonacci.calculate(4)

# 出力: 4 3 2 1 0 1 2 1 0

ご覧のとおり、calculate は同じ n の値で何度も呼び出されています。実際、calculate の呼び出し回数は n に対して指数関数的に増えていきます。

これを回避する方法のひとつが、calculate の結果をメモ化することです。やり方は、これまで見てきた他のメモ化の例と大差ありません。

class Fibonacci
  def self.calculate(n)
    @calculate ||= {}
    @calculate[n] ||= begin
      print "#{ n } "
      if n == 0 || n == 1
        n
      else
        calculate(n - 1) + calculate(n - 2)
      end
    end
  end
end

Fibonacci.calculate(4)

# 出力: 4 3 2 1 0

calculate をメモ化すれば、呼び出し回数が n に対して指数関数的に増えることはなくなります。

Fibonacci.calculate(20)

# 出力: 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

無効化（Invalidation）

メモ化はキャッシュによく似ています。ただし、メモ化された結果は自動的には失効せず、一度設定されると簡単にはクリアできないという大きな違いがあります。

フィボナッチ数列ジェネレータのようなユースケースでは、これはほとんど問題になりません。Fibonacci.calculate(10) は常に同じ結果を返しますからね。しかし、他のユースケースでは話が変わってきます。

たとえば、次のようなコードを見かけることがあります。

# ベストなアイデアとは言えません
# Not the best idea

class User
  def full_name
    @full_name ||= [first_name, last_name].join(" ")
  end
end

個人的には、ここでメモ化は使わないでしょう。姓または名が変更されたとき、フルネームが更新されない可能性があるからです。

多少緩くても許容できる唯一の場所は、Railsコントローラの内部です。次のようなコードは非常によく見かけます。

class ApplicationController
  def current_user
    @current_user ||= User.find(...)
  end
end

これが問題ないのは、コントローラのインスタンスがWebリクエストごとに破棄されるからです。通常のリクエストの途中でログイン中のユーザーが変わることはまずありません。

ActionCableのようなストリーミング接続を扱う場合は、より慎重になる必要があるかもしれません。正直なところ、私は使ったことがないので断言できません。

使いすぎに注意

最後に指摘しておきたいのは、あらゆるものと同様に、メモ化にもやりすぎというものがあるということです。このテクニックは、メモ変数のライフタイムを通じて決して変化せず、しかも計算コストの高い処理にのみ適用すべきものです。