-
-
Save OlaoluwaM/c471a5b12c77882f8bb57c3377ce8a88 to your computer and use it in GitHub Desktop.
High-order function that memoizes a function
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* @summary | |
* 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 all the body of the function is executed, and the result is | |
* added to the cache. | |
* | |
* @see https://www.sitepoint.com/implementing-memoization-in-javascript/ | |
* | |
* @export | |
* @param {Function} func: function to memoize | |
* @returns {Function} | |
*/ | |
function memoize(func) { | |
const cache = {}; | |
return function memoized(...args) { | |
const key = JSON.stringify(args); | |
if (key in cache) return cache[key]; | |
return (cache[key] = func(...args)); | |
}; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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. | |
* | |
* @param {Function} func: function to memoize | |
* @returns {Function} | |
*/ | |
function memoizeTest(func) { | |
var cache = {}; | |
return function memoized() { | |
var key = JSON.stringify(Array.prototype.slice.call(arguments)); | |
if (!(key in cache)) cache[key] = func.apply(this, arguments); | |
console.log('cache:', cache); // remove this | |
return cache[key]; | |
}; | |
} | |
/** | |
* LIMITATIONS | |
* | |
* As memoize is a higher-order function that accepts a function as its argument | |
* and returns a memoized version of the function, it is perfect to work with | |
* pure functions because of the Referential transparency, but it is not good | |
* for a function that modifies itself, e.g. Lazy function definition. | |
*/ | |
/** | |
* Return the value of the number 'x' to the power of 2 | |
*/ | |
function maxPow999(x) { | |
const result = x ** 2; | |
if (result >= 999) { | |
// function is redefined | |
maxPow999 = () => result; | |
} | |
return result; | |
} | |
// creates the memoized version | |
maxPow999 = memoizeTest(maxPow999); | |
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 | |
/** | |
* In the code above, there is a memory leak because the `cache` object created | |
* by the memoized version of `maxPow999` is out of reach, I mean it is no longer | |
* accesible, but still not a candidate to be garbage-collected because of the | |
* own scope created by the `memoize` function. | |
*/ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Return the value of the number 'a' to the power of 'b' | |
*/ | |
function pow(a, b) { | |
return a ** b; | |
} | |
// creates the memoized version | |
pow = memoize(pow); | |
pow(3, 5); // creates the index "[3,5]" and returns 243 | |
pow(6, 2); // creates the index "[6,2]" and returns 36 | |
pow(3, 5); // return the cached result at "[3,5]" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment