Fastest way to join two Javascript/JSON Objects by ID

Question

Assuming I have two Javascript Objects (they have a JSON structure, but are created with JSON.parse()). All entries have a unique ID with which the entries from both objects can be matched. What would be the fastest way to join both objects (native javascript).

The first thing that comes into my mind would be a nested for in loop.

for(var i in firstJson) {
    for(var j in secondJson) {
        if(firstJson[i].id === secondJson[j].id) {
            // join them
        }
    }
 }

Is there a faster way?

@Jorg it would be nice to have two suggestions. First that you will find all the elements from `firstJson` in `secondJson` and second, that you might not find all of them in the other one. — four-eyes, Jan 06 '17 at 12:21
Some small things you can add to improve speed: add a `break` in the if, so as soon as you find the second element you skip other objects; second, remove elements in `secondJson` that have been already merged, so next for loops will be a bit faster — rpadovani, Jan 06 '17 at 12:23
for loop as in question is a better way. `.map` may help , implementation is purely based on json — NiRUS, Jan 06 '17 at 12:25
[See the below link this might help you](http://stackoverflow.com/questions/171251/how-can-i-merge-properties-of-two-javascript-objects-dynamically) — Manoj Sureddi, Jan 06 '17 at 12:28

score 4 · Accepted Answer · answered Jan 06 '17 at 12:27

4

More efficient way would be to create an index out of one of them:

var index = {};
for (var j in secondJson) {
    var obj = secondJson[j];
    index[obj.id] = obj;
};

for (var i in firstJson) {
    var firstObj = firstJson[i];
    var match = index[firstObj.id];
    if (match) {
        // do the stuff
    }
};

This is O(n+m) instead of O(n*m) for nested loops. At the cost of O(m) memory of course.

answered Jan 06 '17 at 12:27

freakish

54,167
9
132
169

This is one good solution. Making use of object accessor as array. – NiRUS Jan 06 '17 at 12:33

score 0 · Answer 2 · answered Jan 06 '17 at 12:45

If both lists are not already sorted you could first sort them by id, then do the comparison and saving the position of the last found object, starting from the last found if nothing was found.

(I do believe that the solution from freakish is faster, but this has no extra memory consumption)

This should be on the order O(nlog(n)+mlog(m)+m)

first.Sort();
second.Sort();


int idx = 0;
int lastIdx = 0;
for (int i = 0; i < first.Count; i++) {
  for (int j = idx; j < second.Count; j++)
  {
    if (first[i] == second[j])
    {
      Console.WriteLine("equal " + first[i]);
      idx = j + 1;
      lastIdx = idx;
      break;
    }
  }
  if (idx == second.Count)
    idx = lastIdx;
}

Fastest way to join two Javascript/JSON Objects by ID

2 Answers2