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

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

 

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#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 で初期化されているならこんな感じ。

1 2 3 4 5

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