Hackernoon logoWork Smarter, Not Harder. Memoize It. by@Swordfish

Work Smarter, Not Harder. Memoize It.

image
Randy Hacker Noon profile picture

@SwordfishRandy

JS, React, Redux, Ruby, Rails, SQL, Python

My favorite parts of Computer Science are things that remind me of being human. Believe it or not Computers have this emergent property where as they become more complex they start to do things just like us. We touched on this when I wrote about Recursion. There I discussed how a computer function will call it self over and over until it gets the answer it wants. So very… human of it and to me this touches on problem solving. Memoization can extend this human like quality further.

Very intuitively Memoization is local memorization of the computer program. Lets say you write a function that gets called. If that same function gets called again with the same inputs then it should return the same output. This is known as functional programming which is composed of pure functions; here things are referential and if you replace the function call with the return value of the function the program will behave exactly the same. Below is an example to demonstrate: you can either put square(10) or 100 in your program and it will run similarly:

const square = (x) => x*x 
square(10)   /* square is a pure function that is referential you could place 100 wherever you place square(10) and get the same result */

Memoization is teaching your program to remember in real time. This will be very beneficial to your program and bring the time complexity screeching to a halt. The first thing is to set up an array or object literal that will serve as the memoy(yes that is an intentional joke). Lets play around and create a function that creates human readable phone numbers. We will start by creating a phoneBook object literal to store our phone numbers in.

const phoneBook = {}

Our function will take in a string of numbers and turn it into something that is formatted for a human to know it is a telephone number:

humanPhoneNumber("dddddddddd") //=>(ddd)ddd-dddd
const phoneBook = {}
function humanPhoneNumber(number){ 
    return  phoneBook[`${number}`] = phoneBook[`${number}`] ||  
    "(" + number.substring(0,3) + ")" + number.substring(3,6) +"-"+ number.substring(6, number.length)
}

The first thing this function will do is check to see if our number has already been processed in our phoneBook function. We are setting the object’s key to the unprocessed number and the value will be the processed form returned from the function. If our function finds the number in our phoneBook by the unprocessed key it will just return the processed value. Otherwise it will run the function, process the number, save the number in the phoneBook, then return it.

Lets test out our memoization to see how much time we are saving.

Node.js has a performance.now() function that will create a time stamp. We will use this to test how long our function calls take.

Lets set up a few function calls before the number is in the phoneBook and after to see how long our function is taking. Lets call the function with a new number, then we will call it again and see how long it takes the second time to just use our phoneBook.

image

Lets look what we get in our terminal:

image

Lets discuss that print out above, in the time it took to perform the initial function call was 0.625 milliseconds. As you can see in the picture there is a random number processed by the function. Then we call the function again with the initial phone number. The second time; the time where the number is already in our phone Book took 0.003 milliseconds. Milliseconds are barely perceptible. However if you are working for a phone company and doing this number processing all the time this saved time would begin to gain importance.

Tags

Join Hacker Noon

Create your free account to unlock your custom reading experience.