RMMZ [Javascript] Most efficient way to compare arrays of objects?

ct_bolt

Creator
Veteran
Joined
May 3, 2012
Messages
954
Reaction score
517
First Language
Javascript
Primarily Uses
RMMZ
What is the most efficient way to compare arrays of objects and return only the matches?

How to find and return a new array of only the matches that has matches of color & id;
The rest of the properties can be anything else.

Example:
Code:
const a = [{color:'blue',id:5}, {color:'red',id:7, type:4}, {color:'green',id:7}, {color:'blue',id:20}];
const b = [{color:'red',id:12}, {color:'green', id:7, tag:'extraData'}, {color:'red', id:7, type:4}];
Then the newly created array would be...
Code:
[{color:'green',id:7}, {color:'red',id:7}]
Is the best way really just to iterate through both arrays and check the specified properties and if they match push the the match into a new array? That's the way I'm about to go for now I think...

Thanks for reading. :popcorn:
 
Last edited:

Nolonar

Veteran
Veteran
Joined
Feb 18, 2018
Messages
160
Reaction score
232
First Language
French, German
Primarily Uses
RMMZ
The easiest (but least efficient) way is to loop through array b for each element of array a:
Code:
const result = [];
for (const element of a) {
    const found = b.find(e => e.color === element.color && e.id === element.id);
    if (found) {
        result.push(found);
    }
}
Do not be misled by Array.prototype.find(). This is still a for-loop within a for-loop, which is inefficient because it has complexity O(n^2).

The most efficient way is to use a so-called "hash map" (aka "hash set") or a "hash table" (aka "dictionary"). This allows you to loop through each array only once. Meaning you now have a complexity of O(n), which is as good as it gets. In JavaScript, all objects are dictionaries.
Code:
function getKey(e) {
    return JSON.stringify({color: e.color, id: e.id});
}

const dictionary = {};
for (const element of a) {
    const key = getKey(element);
    dictionary[key] = true;
}

const result = b.filter(e => dictionary[getKey(e)]);
This will give you all the elements in b, for which there is an element in a, that has the same color and id.

You'll obviously have to modify this code depending on your precise need.
My code was based on the fact that you only seemed to care about color and id.

By the way, the result will be:
Code:
[{color:'green', id:7, tag:'extraData'}, {color:'red', id:7, type:4}]
rather than:
Code:
[{color:'green',id:7}, {color:'red',id:7}]
If you really want to get rid of the tag and type, your code will need to look more like this:
Code:
const result = b.filter(e => dictionary[getKey(e)]).map(e => { return { color: e.color, id: e.id }; });
 
Last edited:

Hudell

Dog Lord
Veteran
Joined
Oct 2, 2014
Messages
3,529
Reaction score
3,680
First Language
Java's Crypt
Primarily Uses
RMMZ
I would do something like this:

Code:
const matchingItems = a.filter(item => b.find(({color, id}) => color === item.color && id === item.id));
 

 Masked 

Assistant
Veteran
Joined
Oct 28, 2015
Messages
90
Reaction score
258
First Language
Portuguese
Primarily Uses
RMMZ
If your arrays are small, honestly, i wouldn't care much about asymptotics and go with whatever is more readable (Hudell's solution, for example). This would actually probably be faster too because array traversal is fast.

I'm not very fond of the idea of using a hash map either, because altough the query is O(1) the actual time it takes is usually higher than other methods such as arrays or even binary search trees, specially when the things being hashed are complex like objects with strings and stuff. So i'd use it only if the lists are really big and the constant factor doesn't matter much.

If your arrays are medium-sized (about 200-1000 elements), probably keeping them sorted and doing binary search is best: asymptotically it's O(n log n) and it's probably faster than hashing in practice. The "keeping them sorted" part can also be done with binary search, but insertions could become as bad as O(n) because of element relocation. Still better than sorting the list everytime, which would be O(n log n) for a standard comparison sort, but far worse than the conventional O(1) for unsorted arrays and hash tables. If you're going for something more insert-intensive, maybe a balanced search tree would be better.

I'm not going to try and implement binary search here (and probably embarrass myself with an off-by-one error xd) but there's plenty of references on the internet already. Here's some:


Here's one about trees: https://www.geeksforgeeks.org/implementation-binary-search-tree-javascript/

And some implementations, if you don't want to bother writing them:
 
Last edited:

ct_bolt

Creator
Veteran
Joined
May 3, 2012
Messages
954
Reaction score
517
First Language
Javascript
Primarily Uses
RMMZ
@Nolonar @Hudell @ Masked
Thanks best friends! Thanks for the knowledge drop ;)
Got the info I needed. Think for now at least I will probably go with a variation of what Hudell has shown.

Thanks again! :cutesmile::thumbsup-right:
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Latest Threads

Latest Posts

Latest Profile Posts

Yesterday I made my first step towards eating more healthily.
I saw candy on discount and did not buy it.
"They yearn for what they fear for."
I always told my DA fans how much I hate slot machines. They're fine in games as a risk-and-reward system. But when you're spending REAL MONEY in a Vegas casino to try and hit the jackpot (which very, very few people will), it can really hurt your budget. Gambling is a bad habit, and I don't like wasting my money on a slim chance. Go to Vegas for the experience, not the jackpot.
Took the kids to a corn maze. They gave us a map and had lights at certain points in the maze. Not overwhelming... or underwhelming... just... whelming.
Okay, vacuuming fruit flies out of the air is surprisingly effective.

Forum statistics

Threads
104,398
Messages
1,006,104
Members
135,929
Latest member
raffle
Top