Was ist Memoization? Beispiel in JavaScript

Unter Memoization verstehen wir die Fähigkeit Programme schneller ausführen zu können aufgrund der Tatsache, dass wir vorherige Ergebnisse zwischenspeichern. Dies ermöglicht es z.B., komplexe Berechnungen durchzuführen und weiterhin die Oberfläche für den Benutzer responsive zu halten.

Wollen wir uns einmal ansehen wie eine Memoization umsetzen können und wo wir diese gebrauchen können. Die Referenz Implementierung ist eine Lösung für JavaScript bzw. TypeScript. Die Bibliothek findest du auch auf npm unter: https://www.npmjs.com/package/easy-memoize

Für die Memoization müssen wir uns überlegen wie wir diese umsetzen. Im Grund genommen, besteht die Hauptaufgabe darin, eine assoziative Liste zu führen. Diese Liste hat als Index Wert einen generierten Schüssel aus den Eingabe Parametern und als Wert das Ergebnis. Somit können wir folgendes Formulieren:

const x = heavyCalc(5, 13); // Dauert, und gibt z.B. 2345558203 zurück
const y = heavyCalc(5, 13); // die Parameter sind bekannt sowie die dazugehörige Funktion, somit wird sofort obiger Wert zurück gegeben.

Um das Ganze zu implementieren, können wir uns folgende Beispiel Implementierung auf meiner Bibliothek easy-memoize ansehen.

Nachfolgendes Code Schnipsel ist Copy & Paste tauglich.

const memoCache = new Map();
let maxCacheSize = 10;

export default function easyMemo<T = unknown>(memoFn: (...args: any[]) => T, deps: any[]) {
    // tslint:disable-next-line:no-shadowed-variable
    return (...args: any[]): T => {
        if (memoCache.has(cacheKeyFor(memoFn, deps, args))) {
            return memoCache.get(cacheKeyFor(memoFn, deps, args));
        } else {
            // Calculate result of input function
            const result = memoFn.apply(undefined, args);
            memoCache.set(cacheKeyFor(memoFn, deps, args), result);

            cleanUpMemo(memoFn);

            return result;
        }
    };
}

const getMatchingMapKeysFor = (partialKey: string): string[] => {
    return Array.from(memoCache.keys()).filter((singleKey: string) => singleKey.includes(partialKey));
};

const cleanUpMemo = <T>(memoFn: (...args: any[]) => T) => {
    const matchingKeys = getMatchingMapKeysFor(memoFn.toString());

    if (matchingKeys.length > maxCacheSize) {
        const toRemove = matchingKeys.length - maxCacheSize;
        for (let i = 0; i < toRemove; i++) {
            memoCache.delete(matchingKeys[i]);
        }
    }
};

const cacheKeyFor = (memoFn: (...args: any[]) => unknown, deps: any[], ...args: any[]): string => {
    return `${ memoFn.toString() }-${ deps.map(dep => cacheKeyFromStrategy(dep)).join(",") }-${ JSON.stringify(args) }`;
};

const cacheKeyFromStrategy = (dependency: any) => {
    // Cache Key Strategy:
    // Functions or Array       => .toString()
    // Object                   => JSON.stringify()
    if (typeof dependency === "object"){
        return JSON.stringify(dependency);
    }

    return dependency === null || dependency === undefined ? "" : dependency.toString();
}
1190cookie-checkWas ist Memoization? Beispiel in JavaScript

Kommentar verfassen