TIL Memoization performance
POSTED ON:
TAGS: advanced javascript performance
I probably write about Memoization a lot in this TIL.
Mostly because I find it difficult to explain in detail. Also because I don't find many opportunities to use it.
What is Memoization?
Memoization is an optimization technique used in many programming languages to reduce the number of redundant, expensive function calls. This is done by caching the return value of a function based on its inputs.
Good use case
Double loops? That's some Big O notation stuff here.
const inefficientSquare = num => {
let total = 0;
for (let i = 0; i < num; i++) {
for (let j = 0; j < num; j++) {
total++;
}
}
return total;
};
Let's see the performance costs:
const start = new Date();
inefficientSquare(40000);
console.log(new Date() - start);
// 4400 <-- 4 seconds
const start2 = new Date();
inefficientSquare(40000);
console.log(new Date() - start2);
// 4467 <--- 4.5 seconds later
The first time it took 4 seconds.
The second time it took 4.5 seconds.
Yikes.
A better way:
Memorization. You catch the data if it exists already.
// Takes a reference to a function
const memoize = func => {
// Creates a cache of results
const results = {};
// Returns a function
return (...args) => {
// Create a key for results cache
const argsKey = JSON.stringify(args);
// Only execute func if no cached value
if (!results[argsKey]) {
// Store function call result in cache
results[argsKey] = func(...args);
}
// Return cached value
return results[argsKey];
};
};NOTE: Don't use this in production.
It's for explanation purposes, and I get weirded out seeing JSON.stringify in these situations.
This is the code from the post, and it has a lot of edge cases. A better way would be to use WeakMaps. ref
REF:
via Memoization Understand Memoization in 5 Minutes
Related TILs
Tagged: advanced