Memoization is a technique that is used a lot in Dynamic Programming and in general to speed up algorithms.
Memoization is the same as caching but in functional programming. The Caching mechanism will store the data into a cache store, and that data can be from anywhere (HTTP page, REST call, … etc) , where memoization is specific to cache the results of a function, and it create and maintain the store inside the function itself (so the function will be pure function) and send the store as a parameter into the function arguments.
Python implementation
Python already comes with a built-in memoization function, but for learning purpose let us try to implement the memoization ourselves.
As memoization used mainly in functional programming and in function, it is better to implement it as a Decorator.
We create a decorator and pass to it the calculation function as a parameters.
1def memoize(func):
2 cache = dict()
3
4 def memoized_func(*args):
5 if args not in cache:
6 cache[args] = func(*args)
7 return cache[args]
8
9 return memoized_func
Let us see an example how to use it with the fibonacci calculation:
1@memoize
2def fibonacci(c):
3 if c in [0, 1]: return c
4 return fibonacci(c - 1) + fibonacci(c - 2)
But, we don’t need to implement memoization ourselves, because Python comes with a built-in function to do that.
functools.lru_cache is a decorator function that does that.
1from functools import lru_cache
2
3@lru_cache
4def fibonacci(c):
5 if c in [0, 1]: return c
6 return fibonacci(c - 1) + fibonacci(c - 2)
JavaScript implementation
Again in JavaScript as in Python before we use the idea of higher-order function to build the memoization:
1function memoization(func) {
2 var cache = {};
3 return function(){
4 var key = JSON.stringify(arguments);
5 const args = Array.prototype.slice.call(arguments);
6 if (!(key in cache)){
7 val = func.apply(null, vv);
8 cache[key] = val;
9 }
10 return cache[key]
11 }
12}
The code above is ceating a higher order function that takes a function as an argument.
In order to make it general we should create a cache that match all arguments as one key. The way to do that is to convert the arguments to a unique string. The way to do that is to convert using JSON.stringify.
The second step is to capture all arguments as an array to pass them to calling the function later.
Let’s use the function as follows:
1function fibonacci(c) {
2 if (c < 2) return c;
3 return fibonacci(c -1 ) + fibonacci(c - 2)
4}
5
6fibonacci = memoization(fibonacci);
7
8const val = fibonacci(46);