Memoization
It’s pretty amazing how much faster caching makes code. I was doing a CodeWars exercise trying to go through an array and find the first (left most) pair of numbers which add up to a given sum (s
). I first tried:
1 2 3 4 5 6 7 8 |
|
Pretty self explanatory, it goes through the array and for every number goes through all the numbers before that one to see if they add up to the sum. It works, but was too slow and timed out when the array was huge.
I tried to speed things up a bit by using indexOf() rather than a second for loop, but that actually slowed things down, as indexOf() is like a loop, but with a bunch of checks included in it.
1 2 3 4 5 6 7 |
|
I then thought about caching or memoization, and that is where the solution lay. Basically, the trick is to create a JavaScript object which holds all the values which have already been seen in the ints
array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|