获取两个对象数组之间差异的有效方法? [英] An efficient way to get the difference between 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} ];

我想获取在 a 中但不在 b 中的对象.这个例子的结果是:

{'id': 20} 和 {'id': 10}.

因为数组可能很大，所以我需要一种有效的方法来做到这一点.

解决方案

//制作 B 中 id 的哈希表var bIds = {}b.forEach(函数(对象){bIds[obj.id] = obj;});//返回 A 中的所有元素，除非在 B 中返回 a.filter(function(obj){返回 !(obj.id in bIds);});

非常小的附录:如果列表非常大并且您希望避免 2 倍额外内存的因素，您可以首先将对象存储在哈希图中而不是使用列表，假设 id 是唯一的: a = {20:{etc:...}, 15:{etc:...}, 10:{etc:...}, 17:{etc:...}, 23:{等:...}}.我个人会这样做.或者:其次，javascript 就地对列表进行排序，因此它不会使用更多内存.例如a.sort((x,y)=>x.id-y.id) 排序会比上面的更糟糕，因为它是 O(N log(N)).但是，如果您无论如何都必须对其进行排序，则有一个 O(N) 算法涉及两个排序列表:即，您将两个列表放在一起考虑，并重复从列表中取出最左边(最小)的元素(即检查，然后递增您获取的列表中的指针/书签).这就像归并排序一样，但要更加小心地找到相同的项目……而且编码起来可能很麻烦.第三，如果列表是遗留代码，并且您想将其转换为没有内存开销的哈希映射，您也可以通过重复从列表中弹出元素并放入哈希映射来逐个元素地执行此操作.>

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.

这篇关于获取两个对象数组之间差异的有效方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！