Safe and Smart Memoization in C++ (or Python)

エレガントなメモ化のやり方

 

同僚から教えてもらったテクニックを忘れそうになったのでメモ。

#include <cstdio>

int memo[100][100];

int main() {
  memset(memo, -1, sizeof memo);
  // call f with parameters
  f(???, ???)
}

int f(int x, int y) {
  int& res = memo[x][y];
  if (res < 0) {
    // do the work when the value has not been calculated
    res = ???
  }
  return res;
}

適当なn次配列をメモ化の領域として使い、1のビット(-1)で初期化するところまでは一般的なやり方。

ポイントは、実際にメモ化したデータを使う部分。
はじめに配列の要素の参照を取り、初期状態でない場合にのみその値を更新する。
いずれのケースでも最後にその参照を返す。

これで処理の流れがシンプルになるし、メモの更新し忘れを防ぐこともできる。




同様に、Python で値が None で初期化されているならこんな感じ。

def f():
    if cache is None:
        # do the work
        cache = ???
    return cache