One classic CS question is to create Fibonacci sequence. One of the solutions is a recursive function and it looks something like this:
function fib(n) {
if (n === 0 || n === 1)
return n;
else
return fib(n - 1) + fib(n - 2);
}
A major problem with recursive fibonacci function above is that it is an expensive function. It calls itself too many times. Calling fib(40) took about 30 seconds on my poor 2015 Macbook air (it calls itself 102,334,155 times), fib(45) almost 5 minutes (calls itself 1,134,903,170 times - a billion time).
Good luck calling fib(100).
Is there anything we can do to shorten an expensive function like this?
Memoization (rhymes with memorization) is a technique in CS to save previous result into a cache so when the function is called again with same argument, it would just return value from the cache and execute the function again. It is useful for expensive functions like fibonacci.
We can use:
const fib = (function() {
const cache = {};
function f(n) {
let value;
if (n in cache) {
value = cache[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);
cache[n] = value;
}
return value;
}
return f;
})();
(Source: here. All credit for above goes to author).
Try the function above and run fib(40), fib(50), and even fib(100). You'll feel the difference.
It stores values on JS object (const cache = {};
) so if the same value is called again, it will fetch the value from cache
instead of executing the function.
Let's say we want to call fib(5). When fib(5) is called the first time, since cache is empty and it could not find 5 in cache (if (n in cache)
is falsy), it executes fibonacci logic (value = f(n - 1) + f(n - 2);
) and then saves the result to cache (cache[n] = value;
). Now we have a cache for n = 5
- something like this: {5: 5}
(btw, value of fib(5) is 5).
The next time we call fib(5) again, it finds ({5: 5}
) in cache. Instead of executing fib(5) again, it simply returns the value from cache lookup value = cache[n]; ... return value;
. Since our fibonacci is recursive, when we call for fib(5), it automatically fills up the cache with values up to 5. Calling fib(5) creates cache for fib(4), fib(3), etc.
Another example is, say we have just called fib(49) and we want to call fib(50) next. Before we call fib(50), inside our cache, we would have cache values like this:
{
0: 0,
1: 1,
2: 1,
3: 2,
...
48: 4807526976,
49: 7778742049
}
We already have values from 0 to 49! All we need to do is to call value = f(n - 1) + f(n - 2);
- aka fib(49) + fib(48), which we already have stored in cache! This is how memoized fib(50) returns the result almost instantaneously compared to its non-memoized version.
Unfortunately, not everything is memoizable. We can only memoize pure functions.
To be a pure function, it must:
Pure function is out of this article's scope, but check this short article on pure function.
Memoization is awesome. But let's not overuse it. Some things to consider when deciding when to use memoization:
Yup. VueJS utilizes memoization. cached(fn)
is a memoization wrapper.
function cached (fn) {
var cache = Object.create(null);
return (function cachedFn (str) {
var hit = cache[str];
return hit || (cache[str] = fn(str))
})
}
And it is being used several times:
const camelizeRE = /-(\w)/g
export const camelize = cached((str: string): string => {
return str.replace(camelizeRE, (_, c) => c ? c.toUpperCase() : '')
})
export const capitalize = cached((str: string): string => {
return str.charAt(0).toUpperCase() + str.slice(1)
})
const hyphenateRE = /\B([A-Z])/g
export const hyphenate = cached((str: string): string => {
return str.replace(hyphenateRE, '-$1').toLowerCase()
})
You can find these function here. (Vue 2.5.0 at the moment of this writing. It might change in the future but you could always go back to previous version).
Happy hacking!
More readings on memoziation:
On pure function: