javascript - 如何高性能地从两个数组中提取子数组？

Question

我有两个 JSON 对象数组:

• 一个包含大约 60,000 个元素，代表我的引用数据集。里面的每个 JSON 都拥有一个键和一些其他属性。请注意，数组中的键可能不是唯一的。
• 另一个包含不同数量的元素(至少几千个)。内部的每个 JSON 都拥有一个键(也在第一个数组中定义)和一些其他属性。

例如:

let refarray = [{key : 1, attr1 : 'aze', ...}, {key : 1, attr1 : 'zer', ...},{key : 2, attr1 : 'ert'},...]
let otherarray = [{key : 1, attr2 : 'wxc', ...}, {key : 3, attr2 : 'xcv'},...]

我只需要从 refarray 中提取其键存在于 otherarray 中的所有元素。

目前我正在使用 loadash，如下所示:

let newarray = _.filter(refarray , function(d) { return _.findIndex(otherarray , function(s) { return s.key=== d.key;}) >= 0});

但是需要 3 到 15 秒，这太长了。欢迎任何最快的解决方案。谢谢。

Answer 1

您可以尝试缓存otherarray的键，然后过滤refarray。我尝试了一个小样本(尽管我在 node 而不是浏览器上尝试过)，并且花费了 100 多毫秒:

let refarray = []
let otherarray = []

for(let i of Array(60 * 1000).keys())
  refarray.push({ key: 1 + (i % 1200) })

for(let i of Array(1000).keys())
  otherarray.push({ key: i + 1 })

console.time('cache')
let cache = _.uniq(_.map(otherarray, n => n.key))
const inCache = n => cache.indexOf(n.key) !== -1

let newArray = _.filter(refarray, inCache)

console.timeEnd('cache')
console.log(refarray.length, otherarray.length, newArray.length);