wong2 - 1 year ago 92
Javascript Question

# An efficient way to get the difference between two arrays of objects?

I have two arrays of objects:

``````var a = [  {'id': 20},   {'id': 15},   {'id': 10},   {'id': 17},   {'id': 23}  ];

var b = [ {'id': 90},   {'id': 15},    {'id': 17},   {'id': 23}  ];
``````

I'd like to get objects which are in a, but not in b. Results from this example would be:

`{'id': 20}`
and
`{'id': 10}`
.

Because the arrays could be large, I need an efficient way to do this.

``````// Make hashtable of ids in B
var bIds = {}
b.forEach(function(obj){
bIds[obj.id] = obj;
});

// Return all elements in A, unless in B
return a.filter(function(obj){
return !(obj.id in bIds);
});
``````

very minor addendum: If the lists are very large and you wish to avoid the factor of 2 extra memory, you could store the objects in a hashmap in the first place instead of using lists, assuming the ids are unique: `a = {20:{etc:...}, 15:{etc:...}, 10:{etc:...}, 17:{etc:...}, 23:{etc:...}}`. I'd personally do this. Alternatively: Secondly, javascript sorts lists in-place so it doesn't use more memory. e.g. `a.sort((x,y)=>x.id-y.id)` Sorting would be worse than the above because it's O(N log(N)). But if you had to sort it anyway, there is an O(N) algorithm that involves two sorted lists: namely, you consider both lists together, and repeatedly take the leftmost (smallest) element from the lists (that is examine, then increment a pointer/bookmark from the list you took). This is just like merge sort but with a little bit more care to find identical items... and maybe pesky to code. Thirdly, if the lists are legacy code and you want to convert it to a hashmap without memory overhead, you can also do so element-by-element by repeatedly popping the elements off of the lists and into hashmaps.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download