Posted on Jul 31, 2020

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, };

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; }

Add a function to check expiry

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

Pass expires flag when creating a new node

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

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; }

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 })();

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--; } }

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; }

Update the test above, add a print at the end

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

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 })();