Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
June 23, 2020 06:53 am GMT

Oi You! Stop Requesting Everything: A Simple Guide to Memoization

Oi you, stop making expensive function calls to request the same data you just retrieved 2 minutes ago! How, you ask? well thats easy, using memoization of course.

Definition

Memoization is an optimization technique in dynamic programming, which involves storing the values of expensive function calls in memory, so that when you need to retrieve these values again, you can do so much, much quicker!

Aims

  • To understand the basic concepts of memoization.
  • To recognise when you should use memoization.
  • To recognise when you should not use memoization.

Prerequisites

Although not necessary, this article will be better understood if you already have some knowledge of:

Overview

Memoization is a form of caching, which involves storing the return value of a function in memory. When the function is called, the cache object is checked to see if the value already exists for the input passed, if it does, then the cached result is returned. If it does not exist in the cache, then the heavy computation is done, and the returned value is also stored in the cache, to be retrieved quicker the next time it is needed.

Lets take a look at a basic example...

Basic Example

1. Lets create a closure

We use a closure to encapsulate our cache object, which we initialise as an empty object. We also add the function which will be checking the cache, and doing the heavy work.

const memoizeFn = () => {  // our cache object  let cache = {};  return (input) => {    // the contents of the function which will be doing the heavy work  }}

2. Lets create our function within the closure

In this example, we will be using a function which doubles the input, which is clearly not a high demanding function, but it serves for this example.

const memoizeFn = () => {  let cache = {};  return (input) => {    const result = input * 2;    return result;  }}

3. Now, time to memoize

All we really need to do, is add an if..else condition in our inner function, to see if the value exists in the cache.

const memoizeFn = () => {  let cache = {};  return (input) => {    // lets log our cache here so we can see what is stored    // when we call our function    console.log(cache);    // have we got the result of this input already from a previous call?    if (cache[input]) {     // nice, we do! No need for any heavy computation here!      return cache[input];    } else {      // its not in our cache!      const result = input * 2;      // store the result in the cache so next time it is called with this input      // we can retrieve it from our cache      cache[input] = result;      return result;    }  }}

As you can see from the example above, we have a closure, memoizeFn, which initialises our cache with an empty object, and returns a heavy computational pure function, which takes a number as an input. This input is used as our key in the cached object. Each time the function is invoked, the cache is checked to see if we already have a result for our input.

4. Lets see it in action

// this invokes the first function and initialises our cache objectconst doubleInput = memoizeFn();doubleInput(10); // console log = {}doubleInput(20); // console log = {10: 20}// 10 is in our cache. No heavy computation neededdoubleInput(10); // console log = {10: 20, 20: 40}

The memoizeFn is invoked and assigned to the doubleInput variable, this variable can now access the cache object when it is invoked. First we call doubleInput with the value 10, at this point our cache object is empty, so the heavy computation of doubling this number needs to be done. Next, we pass 20 as our input, again, the this needs to run through the heavy computation section of the function as it does not exist in our cache. Finally, we pass 10 again to our function, the cache object is checked to see if a value with the key 10 exists, which it does, so the value is retrieved from the cache!

So, Where Would I Use This in the Real World?

Lets take a look at a more real-world example. Say you are creating a SPA social media platform where a user can have a list of friends, and when the user clicks on one of their friends, it returns that users profile. We will need to call an API which returns the data related to that profile, right? Correct. But what if the user, as they are navigating round the website, returns to a profile they visited previously, do we want to call that API again? We could, or we could use memoization. Heres how:

const memoizeUser = () => {  let cache = {};  return async (userId) => {    if (cache[userId]) {      return cache[userId];    }    // it's not in our cache, we need to hit the API    // this could take a little while...    const data = await fetch(`https://myapi.com/users/{userId}`);    const user = await data.json();    cache[userId] = user;    return user;  }}

Heres is our function, which looks very similar to our first example. Next, lets see how we can use it.

// get access to the cacheconst getUser = memoizeUser();// add a click event listener to a button which gets a users profile// this button will have an id of the users id that it accessesdocument.querySelector('#getUserButton').addEventListener('click', async (e) => {  const userId = e.target.id;  // have we visited this user before?   const userData = await getUser(userId);   // rest of function which returns users profile using the  // userData retrieved above});

when a users profile is clicked, we get the user id from the button, we then call getUser, which returns the users data. This will hit an API, unless we already have it in our cache from previously visiting this users profile, which in this case, the call to the server is not necessary, and we can get the data directly from the cache.

Simple, right? This covers the basics of memoization.

Time to Take it up a Notch

If you want to be really clever, you could even pass the heavy computational function to the closure itself, which could take a variable amount of arguments.

const memoize = (fn) => {  let cache = {};  return (...args) => {    // as this now takes variable arguments, we want to create a unique key    // you would need to define this hash function yourself    const key = hash(args);    if (!cache[key]) {      cache[key] = fn(...args);    }    return cache[key];  }}// some functions we can pass to memoizeconst add = (num1, num2) => num1 + num2;const subtract = (num1, num2) => num1 - num2;// these 2 will have different cache objects thanks to closuresconst add2Numbers = memoize(add);const subtract2Numbers = memoize(subtract);const result1 = add2Numbers(10, 20);const result2 = add2Numbers(20, 30);const result3 = subtract2Numbers(10, 5);

Pretty cool, right? We can define this memoize wrapper, and pass a number of functions to it, which each take a variable amount of arguments.

Some Do's and Don'ts

When can memoization be useful?

  • When retrieving fixed data from an API.
  • When performing demanding computation which may regularly reoccur for a given input.

When not to use memoization

  • When retrieving data from an API whose data changes regularly.
  • Simple function calls.

To Summarise

  • Memoization is a form of caching, which stores the result of a demanding function.
  • It is a simple technique which can be easily implemented in to existing code-bases to improve performance.
  • Memoization is useful when dealing with fixed-data APIs, and regularly-occurring heavy computational functions.

Original Link: https://dev.to/jrdev_/oi-you-stop-requesting-everything-a-simple-guide-to-memoization-24n4

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To