DEV Community

Cover image for Build a function memoizer [Part-4]
Kailash Sankar
Kailash Sankar

Posted on

1

Build a function memoizer [Part-4]

In the final part of the series we'll be adding expiry to cached values.

Breakdown:

  • Just like the cacheSize we'll accept an expiresAt param with value in ms.
  • If it's present then each node should store a timestamp of when it was created
  • after finding a node we have to check if it expired
  • clean expired nodes

Update cache options

  let options = {
    cacheSize: DEFAULT_CACHE_SIZE,
    expiresAt: null,
    ...params,
  };
Enter fullscreen mode Exit fullscreen mode

Update Node structure

function Node(key, value, expires) {
  this.key = key;
  this.value = value;
  this.next = null;
  this.prev = null;
  this.timestamp = expires ? Date.now() : null;
}
Enter fullscreen mode Exit fullscreen mode

Add a function to check expiry

Node.prototype.hasExpired = function (diff) {
  if (diff && this.timestamp) {
    return Date.now() - this.timestamp >= diff;
  }
};
Enter fullscreen mode Exit fullscreen mode

Pass expires flag when creating a new node

// inside add function
const node = new Node(key, value, options.expiresAt);

Enter fullscreen mode Exit fullscreen mode

Update find function to ignore an expired node

  // check for cached node
  function find(key) {
    if (key in hash) {
      const node = hash[key];
      if (!node.hasExpired(options.expiresAt)) {
        refresh(node);
        return node;
      }
      // TODO: remove expired node
    }
    return null;
  }
Enter fullscreen mode Exit fullscreen mode

Time for some tests,

(async function () {
  // expires after one second
  const testCache = Cache({ cacheSize: 3, expiresAt: 1000 });

  testCache.add("1-2", 3);
  testCache.add("2-3", 5);
  testCache.add("5-5", 10);
  testCache.add("4-2", 6);

  console.log(testCache.find("2-3")); // returns Node

  // wait for 2 seconds
  await new Promise((r) => setTimeout(r, 2000));

  console.log(testCache.find("2-3")); // returns null
})();
Enter fullscreen mode Exit fullscreen mode

Find returned null for "2-3" because it expired after one second.

To remove expired nodes we have to modify the remove function to remove any node passed to it rather than just the tail node.

  function remove(node) {
    if (node) {
      delete hash[node.key];

      // if the node is in the middle
      if (node.prev) {
        node.prev.next = node.next;
      }
      if (node.next) {
        node.next.prev = node.prev;
      }
      // if it's the tail node
      if (node === tail) {
        tail = node.prev;
      }
      // if it's the head node
      if (node === head) {
        head = node.next;
      }
      size--;
    }
  }
Enter fullscreen mode Exit fullscreen mode

Also update the existing call in the add function to remove(tail)

Update the find function to remove expired nodes

  function find(key) {
    if (key in hash) {
      const node = hash[key];
      if (node.hasExpired(options.expiresAt)) {
        remove(node);
      } else {
        refresh(node);
        return node;
      }
    }
    return null;
  }
Enter fullscreen mode Exit fullscreen mode

Update the test above, add a print at the end

console.log(testCache.print());
// output: "[4-2: 6] -> [5-5: 10]"
Enter fullscreen mode Exit fullscreen mode

Referring an expired node removed it from the linked list. The cache is working, let's test the memoizer

(async function () {
  let count = 0;
  function add(a, b, c = 0) {
    count++;
    return a + b + c;
  }
  const memoAdd = memoizer(add, { cacheSize: 3, expiresAt: 1000 });

  memoAdd(5, 3);
  memoAdd(3, 3);
  memoAdd(1, 2);
  memoAdd(2, 4);
  console.log(count); // 4

  await new Promise((r) => setTimeout(r, 2000));

  memoAdd(1, 2);
  console.log(count); // 5, cache expired

  memoAdd(1, 2);
  console.log(count); // 5, pulled from cache

  memoAdd(2, 4);
  console.log(count); // 6, expired value
})();
Enter fullscreen mode Exit fullscreen mode

Works as expected, we are done with a good enough implementation of a memoizer function with support for cacheSize and expiry.

The memoizer code and jest tests can reviewed here

That's all folks :)


Photo by Steve Johnson on Unsplash

SurveyJS custom survey software

JavaScript UI Libraries for Surveys and Forms

SurveyJS lets you build a JSON-based form management system that integrates with any backend, giving you full control over your data and no user limits. Includes support for custom question types, skip logic, integrated CCS editor, PDF export, real-time analytics & more.

Learn more

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay