获取两个对象数组之间差异的有效方法？

发布于 2024-11-23 19:02:09 字数 330 浏览 4 评论 0原文

我有两个对象数组：

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}。

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

原文

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

玩套路吗 2024-11-30 19:02:09

// 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);
});

非常小的附录：如果列表非常大并且您希望避免 2 倍的额外内存，您可以首先将对象存储在哈希图中，而不是使用列表，假设 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) 算法：即，您将两个列表一起考虑，并重复从列表中取出最左边（最小）的元素（即检查，然后递增）您所取列表中的指针/书签）。这就像合并排序一样，但要更加小心地找到相同的项目......并且可能对编码来说很麻烦。第三，如果列表是遗留代码，并且您希望将其转换为哈希图而不需要内存开销，您也可以通过重复将元素从列表中弹出并放入哈希图中来逐个元素地执行此操作。

// 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.

回复收藏 0 原文

红ご颜醉 2024-11-30 19:02:09

在 lodash 4.12.0 中，您可以使用 _.differenceBy。

_.differenceBy(a, b, 'id');

With lodash 4.12.0 you can use _.differenceBy.

_.differenceBy(a, b, 'id');

回复收藏 0 原文

沦落红尘 2024-11-30 19:02:09

执行此操作的一般方法是：

将 b 中的所有对象放入哈希表中，
对 a 进行迭代，对于每个项目检查它是否在哈希表中。

如今，许多编程环境都有 set 和/或 HashSet 实现，这使得它非常有用。简单地做到这一点。

在特殊情况下，其他方法可能会更有效。例如，如果您的元素是字节大小的值，并且 a 和 b 都相当大，那么我将使用包含 256 个元素的布尔数组“flags”，将所有元素初始化为 false。然后，对于 b 的每个元素 x，将 flags[x] 设置为 true。然后迭代 a，对于 a 中的每个 y，检查是否设置了 flags[y]。

回复收藏 0 原文