Originally published at www.carloscaballero.io on February 8, 2019.
What means Memoization?
The definintion of memoization from the wikipedia is the following:
In computing, memoization or memoisation is an optimization technique used
primarily to speed up computer programs by storing the results of expensive
function calls and returning the cached result when the same inputs occur
again.
Memoization is a programming techique which allows reduce the function’s time
cost for space cost. That is, the functions which are memoized gains speed
for a higher use of memory space.
The memoization only can be used in pure functions, so the first point is known
that is a pure function
In the following animation you can see the final result of applied memoization
in our code.
What is a pure function?
A pure function is a function that meets the following criteria:
- It is a function that always returns the same result when the arguments are the same. For example, the following functions are impure:
- Functions which use random numbers.
- Functions which use datetime as seed to generate the result.
- It is a function that does not produce side effects in the application:
- Data mutation or change application state.
- Network request.
- Database or file request.
- Obtaining user input.
- Querying the DOM.
Benefits
The pure functions are being used in the web develop due to several benefits.
Although, the pure functions are not only use in the web develop. Well, the main
pure function’s benefits are:
- Your code is more declarative which is focus in what must to do and doest not in how must to do. Also, the functions are focus in how different inputs are related to outputs.
- The code is more testability, and find bugs is more easy that in impure functions.
But, in the real life there are side-effects and it is a good part of the code
(for example, when you access to the database or communicate different servers
to request information about the system). So, pure functions are a part of your
code, and you need to know when you can use a pure functions and when you can
use memoization in your code.
Pure functions example
Recursive functions frequently use the pure functions, the most classical
recursive problem is the factorial.
But the imperative version of the function factorial is pure too, because the
pure functions is related with inputs and outputs. In both case when the input
is the same the output will be the same.
Another interesting examples of pure functions are the following:
Memoization in recursive functions
The memoization is the programming technique which allows doesn’t recalculated
the value of the pure function. I.e, the pure functions returns the same value
when have the same inputs. So, the value return can be store in the system using
any cache system (for example a map or array). So, if you calculate the value of
factorial(1)
you can store the return value 1
and the same action can be
done in each execution. So, when you run the factorial(100) you take a while the
first time but the second and more times the time will be reduced!
In this case, if you note the recursive factorial version, you can note that
this version execute several times the function factorial
which can be cache
in our system (using memoization) but if you use the imperative factorial
version your performance will be worse. For this reason, memoization
is a good
known technique in declarative languages.
Memoization Example! — Live code!
In this section I’m going to show you how implement memoization using closure
and the decorator
pattern using JavaScript.
The decorator pattern allows add new features to any object in runtime using
composition instead of hierarchy. The pattern goal is avoid create a class
hierarchy of our features.
A good example to understand this pattern can be found in the Addy Osmany’s
Blog.
So, a basic implementation of memoize decorator in JavaScript is the following:
- Define the cache in which the execution’s result will be store. We use a object
as
map
to store this results. - The decorator returns a new function which has the same behaviour that original function but memoization is implemented.
- The key of the key-value map is generated using the
stringify
and args from the original function. - The
result
of the new function will be - The execution of the original function (
fn(...args)
) whether there is not store in the cache. - The value stored in the cache (whether there is pre-calculated previously).
- The
result
is returned.
How to used our memoized
decorator ?
The way to used this decorator using JavaScript is very easy:
In this case the add
function is the original function without memoization and
the addMemoized
function is the new function which has the new feature
(memoization) using the decorator pattern.
A real demo using memoization!
Now, I’m going to show you a real deam using memoization. Imagine a complex
algorithm that indicate you if an array
has a unique value (as the
Array.prototype.some
) but horribly programmed.
The following step is run the original code and the code using memoization and
compare the time use in each function. It is very important remember that the
original code is not modified but the memoization feature is added.
The following function is used to measure the time used in each execution.
The array are generated at the begin of the script:
And finally, when the user click in a button the functions are execute.
- No memoization
- Memoization
The result is shown in the following animation:
Conclusions
The memoization has been widely developed in web development using TypeScript
or JavaScript
. The following list of resources must be the starting point to
use them in your projects.
Fast-Memoize
use this graph to compare different implementations of memoize:
- The GitHub project is https://github.com/Caballerog/blog/memoization
Originally published at www.carloscaballero.io on February 8, 2019.
Hi! My name is Carlos Caballero and I’m PhD. in Computer Science from Málaga,
Spain. Teaching developers and degree/master computer science how to be experts!
Top comments (11)
Good job, important concepts explained with easy words.
Small improvements to your
memoize
method:undefined
is actually a valid value for a function response. Probably should usehasOwnProperty
instead ofcache[stringifiedParams] === undefined
Thanks for the article.
Hi Enrique!
Thanks for your words, the intend in this post is show the memoization concept (I think that you can find in your language/framework/tool this technique to applied in your project).
Respect your words in the
memoize
method:hasOwnProperty
as you said!At the moment, I could to do a new version to teach in my class. Thanks very much for your comments :-).
I find it's best to use a
Map
or, for functions and other objects, aWeakMap
.The way I write my code, structural comparison will give almost no advantage, but
JSON.stringify
of huge objects will add overhead to every call (even a cache hit)Hi Mihail!
Good catch! In fact, the lodash implementation (github.com/lodash/lodash/blob/508d...) use map.
In my article, I only wanted show the memoization technique when you've a pure function!
In case that you want use it in a real project, I think that lodash implementation is a good option.
I have so many comments about that function :/
memoize.Cache
, but can't set it in the call tomemoize
(likememoize(fn, resolver, cacheClass)
)memoize(fn, resolver, cacheInstance)
, which would be more flexible and no less ergonomic.memoized.cache = cache.set(key, result) || cache
What if my custom cache returns a truthy value that isn't itself? For example if it returnsresult
value? Why not just set it tocache
, what does this achieve? Supporting an immutable cache?The closest I'd go with is something like this:
I don't think
this
support should be there by default, especially passingthis
both to the resolver and the function.Maybe this 😂👌:
Obviously a combinatorial explosion, but that is my point - most of the time you won't use most of the features anywhere in your entire project, so it's better to write your own function. Maybe you want to use a
WeakMap
ofMap
s, or vice versa, instead of a resolver.Memoization is already not a business logic requirement but a performance optimization. So why waste performance on a suboptimal generic solution instead of improving your algorithm by inlining a cache?
Hey, nice article. I've implemented a slightly tweaked version of memoization as well, you can read more about that here: dev.to/ritikesh/why-just-cache-whe....
Cool article!
How did you generate source code example images?
I'm using carbon which you can find as VSCode plugin.
Thanks!
Thanks, I wanted to know that too.
Great article
Really interesting post! I am wondering though- what is "TurboFan"? 🤔
As this wasn't answered and I was also interested, I did a quick Google and found this:
v8.dev/docs/turbofan
"TurboFan is one of V8’s optimizing compilers leveraging a concept called “Sea of Nodes”. "
Obviously, V8 is the name of Google Chrome's JavaScript interpreter, which is what NodeJS is based on.