今回はleetcode 2623を使ってmemoizationについて調べましょう！
Linkはこちら
leetcode : 2623. Memoize
memoizationとは?
Memoization(Memoization)は functionの結果をキャッシングし、同じ入力に対して
キャッシングされた結果を返却します。
これにより、反復的な計算を防止し、性能を最適化できます。
leetcode : 2623の正解
type Fn = (...params: number[]) => number
function memoize(fn: Fn): Fn {
const cache : {[key: string]: number} = {};
return function(...args) : number{
const key = args.toString();
if (cache[key] !== undefined){
return cache[key]
}else{
const result = fn(...args);
cache[key] = result
return result
}
}
}
/**
* let callCount = 0;
* const memoizedFn = memoize(function (a, b) {
* callCount += 1;
* return a + b;
* })
* memoizedFn(2, 3) // 5
* memoizedFn(2, 3) // 5
* console.log(callCount) // 1
*/
study!
今までのキャッシングはredisを使ったんですが、性能を最適化する時memoizationについて考えるようになりました。
アルゴリズムでは以下のように使うことができます。
例はフィボナッチ計算するコードです。
const fibonacci = ((): ((n: number) => number) => {
const memo: Record<number, number> = {};
const fib = (n: number): number => {
if (n <= 1) return n;
if (memo[n] !== undefined) return memo[n];
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
};
return fib;
})();
console.log(fibonacci(10));
console.log(fibonacci(15));
出力
55
610
最後に
日本語の勉強するために作成しておりますので、間違った日本語や内容がありましたらいつでもフィードバックいただければ幸いです。
[참고자료]