javascript 获取两个对象数组之间差异的有效方法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6715641/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
An efficient way to get the difference between two arrays of objects?
提问by wong2
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:
我想获取在 a 中但不在 b 中的对象。这个例子的结果是：
{'id': 20}and {'id': 10}.
{'id': 20}和{'id': 10}。
Because the arrays could be large, I need an efficient way to do this.
因为数组可能很大，所以我需要一种有效的方法来做到这一点。
回答by ninjagecko
// 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.
很轻微的补遗：如果列表是非常大的，你希望避免的2个额外内存的因素，则可以将对象存储在首位，而不是使用列表一个HashMap，假设ID是唯一的：a = {20:{etc:...}, 15:{etc:...}, 10:{etc:...}, 17:{etc:...}, 23:{etc:...}}。我个人会这样做。或者：其次，javascript 就地对列表进行排序，因此它不会使用更多内存。例如a.sort((x,y)=>x.id-y.id)排序会比上面的更糟糕，因为它是 O(N log(N))。但是，如果您无论如何都必须对其进行排序，则有一个 O(N) 算法涉及两个排序列表：即，您将两个列表放在一起考虑，并重复从列表中取出最左边（最小）的元素（即检查，然后递增您获取的列表中的指针/书签）。这就像归并排序一样，但要更加小心地找到相同的项目……而且编码起来可能很麻烦。第三，如果列表是遗留代码，并且您想将其转换为没有内存开销的哈希图，您还可以通过重复从列表中弹出元素并放入哈希图来逐个元素地执行此操作。
回答by Ethan Yang
With lodash 4.12.0 you can use _.differenceBy.
在 lodash 4.12.0 中你可以使用_.differenceBy。
_.differenceBy(a, b, 'id');
回答by user816098
A general way to do this would be:
这样做的一般方法是：
- put all objects from b into a hashtable
- iterate over a, for each item check if it is in the hashtable
- 将 b 中的所有对象放入一个哈希表
- 迭代 a，对于每个项目检查它是否在哈希表中
A lot of programming environments have set and/or HashSet implementations these days, which make it very simple to do this.
如今，许多编程环境都有 set 和/或 HashSet 实现，这使得执行此操作变得非常简单。
In special cases, other ways might be more efficient. If, for example, your elements were byte-sized values, and a and b both fairly big, then I would use a boolean array "flags" with 256 elements, initialize all to false. Then, for each element x of b, set flags[x] to true. Then iterate over a, and for each y in a, check if flags[y] is set.
在特殊情况下，其他方式可能更有效。例如，如果您的元素是字节大小的值，并且 a 和 b 都相当大，那么我将使用具有 256 个元素的布尔数组“标志”，将所有元素初始化为 false。然后，对于 b 的每个元素 x，将 flags[x] 设置为 true。然后迭代 a，对于 a 中的每个 y，检查是否设置了 flags[y]。
回答by Michal
If you not adverse to including a library use underscore.js it has a good intersection function http://documentcloud.github.com/underscore/
如果你不反对包含一个库使用 underscore.js 它有一个很好的交叉功能 http://documentcloud.github.com/underscore/
