Merge array of objects in efficient way

Question

I have below scenario where I am trying to merge two array of objects.

The current code works, but I am looking for a more efficient way.

var constList = [
  { name: "jack", id: "1", designation: "hr" },
  { name: "mary", id: "2", designation: "it" },
  { name: "john", id: "3", designation: "fin" }
]

var apiList = [
  { name: "jack", id: "1", height: "10" },
  { name: "mary", id: "2", height: "20" }
]

var temp = [];

constList.forEach(x => {
  apiList.forEach(y => {
    if (x.id === y.id) {
      temp.push({ ...x,
        ...y
      });
    }
  });
});

console.log(temp);

Only the matching elements from apiList should be merged with constList.

The output is correct, can anyone guide me with best way to to it.

I fail to find fault with your logic as written. If it works, go with it. Don't "worry" a piece of code unless you are truly confronted with a human-measurable problem that *must* be dealt with As Perl programmers like to say, "Tim Toady" = `TMTOWTDI` = "There's More Than One Way To Do It." :-) — Mike Robinson, Dec 18 '19 at 15:42
https://codereview.stackexchange.com would be more suitable for this type of question, imho — Andreas, Dec 18 '19 at 15:42
Maybe "map" would do it, maybe not. And "Map" might wind up being really no faster. — Mike Robinson, Dec 18 '19 at 15:45
Is any of the two lists always a subset (in terms of `id`) of the other? — trincot, Dec 18 '19 at 15:46
There are many questions about this already; did none of the answers on those questions meet your efficiency requirements? — Heretic Monkey, Dec 18 '19 at 15:47
@user804401 you won't be able to achieve the desired outcome with a single loop. — Dan Starns, Dec 18 '19 at 15:47
see the post here (comment from 'Andy') for an alternative approach using `filter` and `some` https://stackoverflow.com/questions/31005396/filter-array-of-objects-with-another-array-of-objects — scgough, Dec 18 '19 at 15:48
The complexity is currently O(m*n) where m and n are the lengths of the lists. This could be reduced by making a hash based lookup like a set, but this won’t necessarily be faster in javascript unless the arrays are quite large. — Mark, Dec 18 '19 at 15:48
Does this answer your question? [Merge 2 arrays of objects](https://stackoverflow.com/questions/7146217/merge-2-arrays-of-objects) — Heretic Monkey, Dec 18 '19 at 15:49
@user804401 ... *"It could be equal or subset"*: which one of the two could be subset of the other? — trincot, Dec 18 '19 at 15:49
I note that in your code you do not actually *merge* (the title has mislead me), but you take an intersection. Is it on purpose that you did not include in `temp` *all* the entries from `constList`? — trincot, Dec 18 '19 at 16:05

trincot · Answer 1 · 2019-12-18T18:06:05.773

2

Your solution is quite OK. Only for very large lists you could benefit from the better time complexity you get from creating a hash map. For instance with a Map:

let constList = [{ name: "jack", id: "1", designation: "hr" },{ name: "mary", id: "2", designation: "it" },{ name: "john", id: "3", designation: "fin" }]
let apiList = [{ name: "jack", id: "1", height: "10" },{ name: "mary", id: "2", height: "20" }]

let map = new Map(constList.map(o => [o.id, o]));
let result = apiList.map(o => ({...map.get(o.id),...o}));

console.log(result);

This assumes that apiList never has any id that does not occur in constList (which is what you confirmed in comments).

The time complexity is O(n+m) here, instead of the O(nm) you get from the nested loop.

Intersection

The above assumes you really wanted to do a merge. I do note however that in your code you do not actually merge the two, but you take the intersection. If that is what you really wanted (intersection), then reverse the roles of the two arrays in the above code, like so:

let constList = [{ name: "jack", id: "1", designation: "hr" },{ name: "mary", id: "2", designation: "it" },{ name: "john", id: "3", designation: "fin" }]
let apiList = [{ name: "jack", id: "1", height: "10" },{ name: "mary", id: "2", height: "20" }]

let map = new Map(apiList.map(o => [o.id, o]));
let result = [];
for (let o of constList) {
    let match = map.get(o.id);
    if (match) result.push({...o, ...match});
}

console.log(result);

edited Dec 18 '19 at 18:06

answered Dec 18 '19 at 15:54

trincot

317,000
35
244
286

what are the implications of converting an array to a `Map`? I would presume this would also affect the time complexity. I still can't see how this would be "more efficient" than the original solution proposed. – Dan Starns Dec 18 '19 at 15:59
1

You do not match the expected output. – sjahan Dec 18 '19 at 16:01
@sjahan, yes the OP asked for a merge, but their code is in fact doing an intersection. I have added a section (pun unintended) to my answer to do an intersection. – trincot Dec 18 '19 at 16:13
@DanStarns, the idea of the map is to avoid a nested loop. It represents a loop, but because it isn't nested it will give a better time complexity. A loop of a loop is not the same as a loop + a loop. The latter will be more efficient when the number of iterations is significant. Note that a Map is built in linear time, and an item can be retrieved by its key in constant time. – trincot Dec 18 '19 at 16:15
Extra parenthesis on the end of `result.push` there – chazsolo Dec 18 '19 at 17:29
Thanks for mentioning, @chazsolo. Corrected my last faulty edit. – trincot Dec 18 '19 at 18:06
@trincot cool, thanks for your explanation :) – Dan Starns Dec 18 '19 at 19:54

score 0 · Answer 2 · answered Dec 18 '19 at 19:52

You may use simple for loop that could increase performance by 10x if used under certain conditions.

As I tested the below code

TEST CASE 1:

Algorithim: YOUR CODE WITH FOR EACH

INPUT SIZE: 150 elements (constList = 100 elements & apiList = 50 elements)

INPUT TYPE: apiList will always match completely with constList. i.e., All 50 elements of apiList will match with 50 elements of constList out of 100 elements.

and measure performance with your code it took ~0.81ms to merge and sort the results.

TEST CASE 2:

Algorithm: BELOW CODE

INPUT SIZE: 1700 elements (constList = 1000 elements & apiList = 700 elements)

INPUT TYPE: apiList will always match completely with constList, i.e., All 700 elements from apiList will match with 700 elements of constList out of 1000 elements.

and measure performance with below code it took ~0.82ms to merge and sort the results.

for(let i =0; i< constList.length;i++){
    flag = true;
    for(let j=0; j<apiList.length;j++){
        if(apiList[j].id == constList[i].id){
            const data = Object.assign({}, constList[i], apiList[j]);
            temp.push(data);
            flag = false;
            apiList.splice(j,1);
            break;
        }
    }
    flag && temp.push(constList[i]) && constList.splice(i,1);
}

Note: Here, the original array will be changed due to deletion operation. So make sure to perform the operation only over clone/duplicate array to preserve original data.

Merge array of objects in efficient way

2 Answers2

Intersection