はじめに
関数キャッシュは重要な概念であり、本質的に時間とスペースを交換するものです。
概要
天気を取得するための別の関数getChanceOfRainが呼び出されるたびに計算に100ミリ秒かかるとします：
import { getChanceOfRain } from "magic-weather-calculator";
function showWeatherReport() {
let result = getChanceOfRain(); // Let the magic happen
console.log("The chance of rain tomorrow is:", result);
}
showWeatherReport(); // (!) Triggers the calculation
showWeatherReport(); // (!) Triggers the calculation
showWeatherReport(); // (!) Triggers the calculation
これは明らかに計算資源の無駄遣いです。天候が一度計算されたのであれば、もう一度計算する必要はありません。 memoizedGetChanceOfRain そこで、結果をキャッシュする関数を作ることができます：
import { getChanceOfRain } from "magic-weather-calculator";
let isCalculated = false;
let lastResult;
// We added this function!
function memoizedGetChanceOfRain() {
if (isCalculated) {
// No need to calculate it again.
return lastResult;
}
// Gotta calculate it for the first time.
let result = getChanceOfRain();
// Remember it for the next time.
lastResult = result;
isCalculated = true;
return result;
}
function showWeatherReport() {
// Use the memoized function instead of the original function.
let result = memoizedGetChanceOfRain();
console.log("The chance of rain tomorrow is:", result);
}
キャッシュを優先的に使用するかどうかを呼び出しごとに判断し、キャッシュがない場合は元の関数を呼び出してキャッシュを記録します。こうすることで、複数回呼び出された場合、最初の1回を除いて、結果はすぐにキャッシュから返されます：
showWeatherReport(); // (!) Triggers the calculation
showWeatherReport(); // Uses the calculated result
showWeatherReport(); // Uses the calculated result
showWeatherReport(); // Uses the calculated result
キャッシュはパラメータを考慮しないためです：
function showWeatherReport(city) {
let result = getChanceOfRain(city); // Pass the city
console.log("The chance of rain tomorrow is:", result);
}
showWeatherReport("Tokyo"); // (!) Triggers the calculation
showWeatherReport("London"); // Uses the calculated answer
多くのパラメータの可能性があるため、3つの解決策があります：
最後の結果のみキャッシュ
最後の結果だけをキャッシュするのが最もストレージ効率がよく、計算エラーもありませんが、パラメータが変更されるとキャッシュがすぐに無効になってしまうという問題があります：
import { getChanceOfRain } from "magic-weather-calculator";
let lastCity;
let lastResult;
function memoizedGetChanceOfRain(city) {
if (city === lastCity) {
// Notice this check!
// Same parameters, so we can reuse the last result.
return lastResult;
}
// Either we're called for the first time,
// or we're called with different parameters.
// We have to perform the calculation.
let result = getChanceOfRain(city);
// Remember both the parameters and the result.
lastCity = city;
lastResult = result;
return result;
}
function showWeatherReport(city) {
// Pass the parameters to the memoized function.
let result = memoizedGetChanceOfRain(city);
console.log("The chance of rain tomorrow is:", result);
}
showWeatherReport("Tokyo"); // (!) Triggers the calculation
showWeatherReport("Tokyo"); // Uses the calculated result
showWeatherReport("Tokyo"); // Uses the calculated result
showWeatherReport("London"); // (!) Triggers the calculation
showWeatherReport("London"); // Uses the calculated result
極端な場合はキャッシュなしと同等：
showWeatherReport("Tokyo"); // (!) Triggers the calculation
showWeatherReport("London"); // (!) Triggers the calculation
showWeatherReport("Tokyo"); // (!) Triggers the calculation
showWeatherReport("London"); // (!) Triggers the calculation
showWeatherReport("Tokyo"); // (!) Triggers the calculation
すべての結果をキャッシュ
2つ目のオプションは、すべての結果をキャッシュし、キャッシュを保存するためにMapを使用することです：
// Remember the last result *for every city*.
let resultsPerCity = new Map();
function memoizedGetChanceOfRain(city) {
if (resultsPerCity.has(city)) {
// We already have a result for this city.
return resultsPerCity.get(city);
}
// We're called for the first time for this city.
let result = getChanceOfRain(city);
// Remember the result for this city.
resultsPerCity.set(city, result);
return result;
}
function showWeatherReport(city) {
// Pass the parameters to the memoized function.
let result = memoizedGetChanceOfRain(city);
console.log("The chance of rain tomorrow is:", result);
}
showWeatherReport("Tokyo"); // (!) Triggers the calculation
showWeatherReport("London"); // (!) Triggers the calculation
showWeatherReport("Tokyo"); // Uses the calculated result
showWeatherReport("London"); // Uses the calculated result
showWeatherReport("Tokyo"); // Uses the calculated result
showWeatherReport("Paris"); // (!) Triggers the calculation
こうすることの欠点はメモリオーバーフローで、可能なパラメータが多すぎるとメモリが無制限に増えてしまい、最悪の場合はブラウザの制限やページのクラッシュを引き起こします。
その他のキャッシュ戦略
最後のアイテムだけをキャッシュする方法と、すべてのアイテムをキャッシュする方法の間には、LRUを使って最近使われたキャッシュだけを最小化する方法や、Mapの代わりにWeakMapを使ってブラウザのリサイクルを促進する方法などがあります。
関数キャッシュの最後の落とし穴として、純粋な関数でなければならないということが挙げられます。例えば、以下のようなCASEです：
// Inside the magical npm package
function getChanceOfRain() {
// Show the input box!
let city = prompt("Where do you live?");
// ... calculation ...
}
// Our code
function showWeatherReport() {
let result = getChanceOfRain();
console.log("The chance of rain tomorrow is:", result);
}
getChanceOfRainは、ユーザーによって何らかのデータが入力されるたびに結果を返すので、キャッシュエラーになります。その理由は、「関数の入力パラメータの一部がユーザーによって入力される」ことが副作用であり、副作用のある関数をキャッシュすることはできないからです。
関数のキャッシュをローカルで行えるように、副作用のある関数の副作用のない部分を分割するのです：
// If this function only calculates things,
// we would call it "pure".
// It is safe to memoize this function.
function getChanceOfRain(city) {
// ... calculation ...
}
// This function is "impure" because
// it shows a prompt to the user.
function showWeatherReport() {
// The prompt is now here
let city = prompt("Where do you live?");
let result = getChanceOfRain(city);
console.log("The chance of rain tomorrow is:", result);
}
最後に、キャッシュ関数は高階関数に抽象化することができます：
function memoize(fn) {
let isCalculated = false;
let lastResult;
return function memoizedFn() {
// Return the generated function!
if (isCalculated) {
return lastResult;
}
let result = fn();
lastResult = result;
isCalculated = true;
return result;
};
}
これにより、新しいキャッシュ関数を簡単に生成できます：
let memoizedGetChanceOfRain = memoize(getChanceOfRain);
let memoizedGetNextEarthquake = memoize(getNextEarthquake);
let memoizedGetCosmicRaysProbability = memoize(getCosmicRaysProbability);
isCalculated と lastResult はどちらも memoize 関数によって生成されたクロージャに格納され、外部からはアクセスできません。
についてもっと読む
関数キャッシュを実装した汎用高次関数
元の例はまだ比較的単純で、関数への複数の引数がどのように処理されるかを考慮していません。そこで、ここではLodash memoize関数のソースコードを分析します：
function memoize(func, resolver) {
if (
typeof func != "function" ||
(resolver != null && typeof resolver != "function")
) {
throw new TypeError(FUNC_ERROR_TEXT);
}
var memoized = function () {
var args = arguments,
key = resolver ? resolver.apply(this, args) : args[0],
cache = memoized.cache;
if (cache.has(key)) {
return cache.get(key);
}
var result = func.apply(this, args);
memoized.cache = cache.set(key, result) || cache;
return result;
};
memoized.cache = new (memoize.Cache || MapCache)();
return memoized;
}
key = resolver ? resolver.apply(this, args) : args[0];
つまり、キャッシュされたキーはデフォルトでは関数実行時の最初のパラメータとなり、リゾルバを通してパラメータを取得することで新しいキャッシュキーに処理することもできます。
func.apply(this, args)パラメータは関数実行時にも渡されます。
lodash.memoize.Cache 最後に、キャッシュはデフォルトのマップを使わず、WeakMapなど、ユーザがカスタマイズして設定できるようになりました：
_.memoize.Cache = WeakMap;
キャッシュが適切でない場合
以下の2つの状況はキャッシュに適していません：
- 実行頻度の低い関数。
- 本質的に実行速度が速い関数。
実行頻度の低い関数については、実行効率を向上させるためにキャッシュを使用する必要はありませんし、キャッシュは長い間メモリを占有します。独自の実行速度が速い関数については、実際には、単純な計算のほとんどは非常に高速ですが、速度の速度にキャッシュの使用が大幅に改善されていないと同時に、計算結果が比較的大きい場合、ストレージリソースを占有します。
これは、次の例のようなリファレンスのバリエーションでは特に重要です：
function addName(obj, name){
return {
...obj,
name:
}
}
objにキーを追加するのはそれだけでも非常に高速ですが、キャッシュを追加することには2つの欠点があります：
- objが非常に大きい場合、完全なobj構造がクロージャに格納され、メモリ・フットプリントが2倍になります。
- obj が mutable によって変更された場合、通常のキャッシュ関数は元の結果を返します。
オブジェクトの深さまで強制的に比較すると、境界の問題は避けられますが、パフォーマンスは著しく低下します。
概要
関数キャッシュはとても便利ですが、すべてのシナリオに使えるわけではありません。したがって、すべての関数にキャッシュを追加するという極端なことはせず、計算に時間がかかり、何度も再利用される可能性があり、純粋な関数に限定しましょう。
