Skip to content

Instantly share code, notes, and snippets.

@jherax
Last active July 17, 2024 01:55
Show Gist options
  • Save jherax/a3208b5c3d342a756008444ad81d8045 to your computer and use it in GitHub Desktop.
Save jherax/a3208b5c3d342a756008444ad81d8045 to your computer and use it in GitHub Desktop.
High-order function that memoizes a function
/**
* High-order function that memoizes a function, by creating a scope
* to store the result of each function call, returning the cached
* result when the same inputs is given.
*
* @description
* Memoization is an optimization technique used primarily to speed up
* functions by storing the results of expensive function calls, and returning
* the cached result when the same inputs occur again.
*
* Each time a memoized function is called, its parameters are used as keys to index the cache.
* If the index/key is present, then it can be returned, without executing the entire function.
* If the index is not cached, then the original function is executed, and the result is
* stored into the cache.
*
* LIMITATIONS
*
* As memoize is a higher-order function that accepts a function as its argument
* and returns a memoized version of the function itself, it's perfect to work with
* pure functions because of the Referential transparency, but it is not suitable
* for a function that modifies itself like the Lazy function definition pattern,
* or for memoizing recursive functions.
*
* @warn Do not use with arguments of type `Object` or `Array`.
* If you need memoize a function with object arguments, then
* serialize the arguments and use it as key.
*
* @param func Function to memoize
* @returns Memoized function
*/
function memoize<K extends unknown[], R>(func: (...args: K) => R) {
const cache = new Map<string, R>();
return function memoized(...args: K): R {
// For performance reasons, it is not recommended
// memoizing functions with `Object` or `Array` arguments,
// but if the body function is really cpu consuming, you can
// serialize arguments, for example, using `JSON.stringify(args)`
// or a better serializer. Map() uses identity comparison for keys
// and, that's why we need to serialize the arguments.
// const key = JSON.stringify(args);
const key = args.toString();
if (cache.has(key)) {
return cache.get(key);
}
const result = func(...args);
cache.set(key, result);
return result;
};
}
/**
* In the code below, there is a memory leak because the `maxPow999` function is redefined
* and the `cache` object created by the memoized version of `maxPow999` is out of reach.
* It is no longer accesible, but still not a candidate to be garbage-collected because of
* the scope created by the `memoizeTest` function.
*/
function memoizeTest(func) {
const cache = Object.create(null);
return function memoized(...args) {
// const key = JSON.stringify(args);
const key = args.toString();
if (!(key in cache)) cache[key] = func(...args);
console.log('cache:', cache); // remove this
return cache[key];
};
}
// creates the memoized version
var maxPow999 = memoizeTest((x) => {
const result = x ** 2;
if (result >= 999) {
// function is redefined
maxPow999 = () => result;
}
return result;
});
maxPow999(30); // creates the index "[30]" and returns 900
maxPow999(31); // creates the index "[31]" and returns 961
// this call redefines the function, overwriting the memoized version
maxPow999(32); // creates the index "[32]" and returns 1024
// these calls are no longer using the cache, because
// it was redefined as maxPow999 = () => result;
maxPow999(30); // => 1024
maxPow999(15); // => 1024
maxPow999(1); // => 1024
/**
* Return the value of the number 'a' to the power of 'b'
*/
function pow(a, b) {
return a ** b;
}
// creates the memoized version
const powMemo = memoize(pow);
powMemo(3, 5); // creates the index "[3,5]" and returns 243
powMemo(6, 2); // creates the index "[6,2]" and returns 36
powMemo(3, 5); // return the cached result at "[3,5]"
@fedeghe
Copy link

fedeghe commented Oct 3, 2018

The usage of JSON.stringify to generalize it is incredibly time-consuming and even the simplest function (like the pow) pays a huge bill. To see it just try to push it a bit maybe testing the Math.pow against his memoized version returned by the memoize in something like a function to compute all narcissistic numbers smaller than 1 billion 🗡️

here a fiddle, .... hint: stay low far below 1E9

@jherax
Copy link
Author

jherax commented Feb 6, 2019

Thanks for your feedback @fedeghe
I saw your useful test-case in fiddle.

Maybe using a hash and a custom serializer can help with the performance.
My first thought was using something like this: How to implement a simple hash table.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment