Hello folks,
Notice I said folks? It has been so long! We’ve all added a year or two since the last newsletter went out. I know we’re past COVID but I hope you have still being keeping safe. I’m particularly happy to be writing this; after all, it has been a while!
When I started out this newsletter, I attempted to explain things as I would to a five(5) year old, today, I assume you are six(6)! Let’s get started!
Memoization: A key to finishing exams on time
The key to finishing examinations is studying.
When taking an examination, your experience of that exam is largely influenced by your knowledge of the content. Consequently, the amount of time you spend on an exam is directly proportional your knowledge and memory. I would argue that it skews towards better memory.
Let’s assume we have these simple math problems:
23/3 * 2 + 9/4
23/3 * 2 + 9/3
They are examples from our math class; we were all in class yesterday, remember? No? Well. Moving on.
Endeavour to solve these before continuing. Write it down.
Have you solved them? Is it noted down?
Continue.
So here is an exam.
What is 23/3 * 2 + 9/4 ?
What is 9 * 4 - 10 + 2^5?
What is 23/3 * 2 + 9/3?
If you wrote down the examples I provided earlier, how do you compare the time you spent each question? Did you spend more time on question two(2)? I would guess so, because it is the first time you are coming across that arithmetic right? You don’t even have to think about questions 1 and 3. You have the answers written down or at the back of your head. See how much time you save when you study? And how exams become easier?
I asked you to write down the results of example equations because it would simulate a lookup. Given that you have previously solved the equation and noted the answer, you can always look up the answer to that question in constant time O(1) without ever needed to resolve the equation. Except of course you lose your note.
This is memoization.
Memoization
Memoization is a technique that allows us save computation time by reusing the results of previous calculations - same or similar. Today, we will be focusing on similar.
Using commutative property of numbers: 3 + 6 = 6 + 3 = 9 AND 4 * 6 = 6 *4 = 24
We can thus say that 3 + 6 is similar to 6 + 3 because the outcome is the same. In essence, if the outcome of an operation is the same as the outcome of a previous similar operation (commutative), we can use memoization to avoid the second operation all together, saving us the computation time spent on it.
Getting Our Hands Dirty with Code
I often code in JavaScript for my newsletters, but I am going to use Python today. You’re welcome.
We are given this array: [6,3,12,5,9,17,20] and our task is to add each number in the array to all the other numbers in the array, such that we have an NxN result composing of all the sums for each number.
Simple and straightforward. O(n^2). No biggie. Our result looks like this:
Here, we add up every number and redo similar calculations like:
6(index 0) + 12 (index 2) and 12 (index 2) + 6(index 0).
9(index 4) + 17(index 5) and 17(index 5 + 9(index 4).
In our example array of length seven(7) we are recalculating twenty one (21) equations. What this means is that instead of performing forty nine(49) calculations, we can perform twenty eight(28). What if these weren’t just simple calculations but expensive comparisons?
How do we avoid repeating the commutative indexes?
Looking back at output, we can see that:
On Row 1, the number at index 0 → 9 is same as the number on Row 0, index 1 → 9.
On Row 2: the number at index 0 → 18 is same as the number on Row 0 index 2 → 18.
Similarly, on Row 2: the number at index 1 → 15 is same as the number on Row 1 index 2 → 15.
We can follow the same pattern on Row 3 till Row 7.
At Row 7, we see that the only new number is 40. Every other number has already been computed by a previous operation. Yet, our program calculates all the numbers.
Let’s change that!
Here, I’ve implemented our observation. That at position i, if i> j, we have performed the commutative operation of j and i. We can retrieve the result of the previous operation and set that as the new result.
As I previously highlighted, at N=7, we skip 21 operations. At N=16, we skip 120 operations.
Why is it important?
If the operation is an expensive, this becomes a really simple way to save time on computation. This is currently saving me hours of computational time as I attempt to build a similarity matrix of 9K documents. Every time I skip a comparison, it saves me 10-30s.
Conclusion
Study for your exams. Reuse your study notes. Always remember that memoization can save you some time.
Note: I was conflicted if I should have written this as Dynamic Programming instead of memoization. Let me know what you think in the comment section.
Arguably the best way I’ve had memoization explained to me.
Thanks for explaining like I’m 6!