以下のfoo関数は中で重い処理を行っているものだとします。
foo(1);
foo(1);
foo(1);上記では3回、引数もまったく同じで状態でfooを実行しているということをしています。もし、fooの結果が、ある引数の時の結果が必ず決まったものになるという関係ならこれは勿体無いことをしていることになります。必ず決まった結果になるのに、丸々重い処理をしているからです。
このような場合は、最初の実行の結果を記録して、次回以降それを返すようにするといいです。
1を渡されて実行された時に初回の実行結果の記録がなければ、関数のメイン処理をそのまま行い、得られた結果を記録次回以降
1を渡されて実行された場合は、前回の結果の記録が残っているので関数のメイン処理は行わず、記録をそのまま返します。
メモ化するにはfoo関数をこのようにします。memoは記録するための Map です。
const memo = new Map();
const foo = num ⇒ {
if (memo.has(num)) {
return memo.get(num);
}
const result = process(); // 重い処理...
memo.set(num, result);
return result;
};最初は記録があるかのチェックをして、あれば記録を返す処理の部分です。これはnumで数値なのでそのままキーとして使っていますが、これがオブジェクトなら新しい参照のオブジェクト化したり、対象のプロパティを取り出したり、JSON.stringifyで文字列にしたりして正規化します。
記録がない場合はその後の処理を行い結果は、正規化したキーの値としてsetするだけです。
試しに測ってみる
const Benchmark = require('benchmark');
const suite = new Benchmark.Suite();
/*
* [
* [98, 24, 34, 1, 0, ...],
* [9, 98, 43, 11, 93, ...],
* [17, 9, 43, 54, 86, ...],
* ...
* ]
*/
const randomIndex = () => Math.floor(Math.random() * 99);
const arr = Array.from(Array(100)).map(container => {
return Array.from(Array(100)).map(() => randomIndex());
});
const nonMemoizeFn = idx => {
return arr[idx].reduce((acc, num) => {
acc += num;
return acc;
}, 0);
};
const memoize = new Map();
const memoizeFn = idx => {
if (memoize.has(idx)) {
return memoize.get(idx);
}
const result = nonMemoizeFn(idx);
memoize.set(idx, result);
return result;
};
suite
.add('memoize fn', () => {
memoizeFn(randomIndex());
})
.add('non memoize fn', () => {
nonMemoizeFn(randomIndex());
})
.on('cycle', event => {
console.log(String(event.target));
})
.on('complete', () => {
console.log(`Fastest is ${this.filter('fastest').map('name')}`);
})
.run({async: true});結果はこのようになります。
memoize fn x 20,497,190 ops/sec ±1.00% (86 runs sampled)
non memoize fn x 754,918 ops/sec ±1.89% (86 runs sampled)
Fastest is memoize fn
