[SOLVED] What's the cheapest method to find all items in a JavaScript map not present in another map?

Issue

I am working quite a bit with Maps in javascript. I need the most computationally efficient way to find all items that are in Map a that are not present in Map b. For example,

const a = new Map();
a.set('item1', 'item1value');
a.set('item2', 'item2value');


const b = new Map();
b.set('item1', 'item1value');

The result of the function I’m looking to write would be another Map, with a single entry of key: item2, value: item2value.

I am well aware of the multitude of questions / answers / methods to do this with arrays and objects, however I have not seen such an explanation for maps. I need the absolute most efficient way to do so, as I will need to be call this function up to thousands of times quickly. Is conversion to an array and back to a Map the best way? Are there any tricks with Maps that may help?

Solution

No, don’t convert the maps to arrays and back. Computing the difference between arrays is slow, in a map you have O(1) lookup. Just loop through the entries of a and put them into the result if you don’t find an equivalent entry in b. This will have the optimal time complexity O(n) (where n is the size of the map a).

const result = new Map();
for (const [k, v] of a) {
    if (v === undefined && !b.has(k) || b.get(k) !== v) {
        result.set(k, v);
    }
}

If you know that your map doesn’t contain undefined values, you can omit the v === undefined && !b.has(k) || entirely and might get some speedup. Also, notice that if your map can contain NaN values, you’ll want to use Object.is instead of ===.

If you want to write it as a single fancy expression, consider a generator:

const result = new Map(function*() {
    for (const e of a) {
        const [k, v] = e;
        if (v === undefined && !b.has(k) || b.get(k) !== v) {
            yield e;
        }
    }
}());

Answered By – Bergi

Answer Checked By – Willingham (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *