This content originally appeared on DEV Community and was authored by jiiin✨
Here is my initial (failed) LeetCode answer for 2630. Memoize II 🙈🙈🙈
function memoize(fn) {
let previousParameters = [];
let cachedResult;
return function(...params) {
// if params and previousParameters array are deep equal, use cached result
const isEqual = isDeepEqual(params, previousParameters);
if(isEqual) {
return cachedResult;
}
// else update previousParameters, call fn(...params), assign result
previousParameters = params.slice();
cachedResult = fn(...params);
return cachedResult;
}
}
const isDeepEqual = (object1, object2) => {
const objKeys1 = Object.keys(object1);
const objKeys2 = Object.keys(object2);
if (objKeys1.length !== objKeys2.length) return false;
for (var key of objKeys1) {
const value1 = object1[key];
const value2 = object2[key];
const isObjects = isObject(value1) && isObject(value2);
if ((isObjects && !isDeepEqual(value1, value2)) ||
(!isObjects && value1 !== value2)
) {
return false;
}
}
return true;
};
const isObject = (object) => {
return object != null && typeof object === "object";
};
isDeepEqual was a method that I normally use in my practice. But this solution fails to differentiate unique parameters. Because previousParameters is a shallow copy of given param, it creates new reference ([o, o] will always differ from next [o, o])
After couple of failures, I (had to) glanced a few solutions 😏 and got a hint that Map object was right way to go! Unfortunately I have no idea what javascript Map object (or Hash Map data structure) is.
To begin with, what is data structure?
Data structure (DS) is a way of organising data so that it can be accessed, queried, updated quickly and easily
There is a related concept called Abstract Data Types (ADT).
Abstract Data Types vs. Data Structure
- Abstract Data Type (ADT) provides the interface
- Interface does not give any specific details or in what programming language
- How Data Structure behave & what method this data structure have is ADT
| Abstraction (ADT) | Implementation (DS) |
|---|---|
| List | Dynamic Array, Linked List |
| Queue | Linked List based Queue, Array based Queue, Stack based Queue |
| Map | Tree Map, Hash Map / Hash Table (here is our map!✨) |
Here I made the second mistake that I simply assigned param as key value.
let localCache = new Map();
if(!localCache.has(params)) {
localCache.set(params, fn(...params))
}
return localCache.get(params)
This solution failed because params in localCache.has(params) method does not compare individual values in params array 😅
For example, const foo = [2, 2] and const bar =[2, 2], foo and bar has different reference therefor it is always unique.
Which implies that Map object is a perfect data structure
when ** a value paired to a single key! **
In other words, to use Map object correctly, I need to create nested Map object from { [2, 2]: 4 } to { 2: { 2: 4 }}
But this approach has one challenge that get method will return a branch instead of result. For example:
fn(1, 2) // { 1: {2: 3 }}
cache.get(1) // will return {2: 3} which is branch not the result 3
To solve it, we need
- a unique key to mark the value as result,
- a local variable that stores the last child map object in nested map so we can extract the result value by get method 🌟
Here is final solution:
const RES = Symbol('result') // 1. a unique key
return function(...params) {
let localCache = new Map(); // 2. a local variable
for(let param of params) {
if(!localCache.has(param)) {
localCache.set(param, new Map())
}
localCache = localCache.get(param)
}
if(!localCache.has(RES)) {
// assign function result in last child
localCache.set(RES, fn(...params))
}
return localCache.get(RES)
}
This question was really great to understand the usage of Map object! Faster querying 💪💪💪
This content originally appeared on DEV Community and was authored by jiiin✨
jiiin✨ | Sciencx (2023-04-16T09:21:34+00:00) JS – Map & Symbol object. Retrieved from https://www.scien.cx/2023/04/16/js-map-symbol-object/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.