JavaScript - 比较非常大的对象数组的有效方法

Question

我有 2 个非常大的数据集，由于环境的限制，我需要在客户端进行比较。

相应的对象数组的大小每个都超过 450k，我一直在测试不同的方法来比较它们(对于循环，.find，.indexOf，.reduce，$.grep(，并且它们都运行得非常慢(每分钟大约 700 次计算(。

检查包括找出其中一个数组中的每个对象是否已包含在另一个数组中，例如：

var Arr1 = [{ID:2, Name: Bar}, {ID:1, Name: Foo}]
var Arr2 = [{ID:2, Name: Fu}, {ID:2, Name: Bar}] 

如果 Arr2中的任何对象被任何属性包含在第一个对象中，在这种情况下 (Arr2[1]。名称 == 到达 1[0]。名称(？会返回true

在这种情况下，我会将其推送到一个新的对象数组，我们可以命名为 Found：Found.push(Arr1[0])

我当然需要对数组中的所有 400k+ 对象执行此检查，因此它变得非常慢。

我知道我的请求中有几个"但是"，例如可用的 RAM 和处理器速度，但假设环境完美，最快的方法是什么？

Answer 1

我认为最重要的是确保你的复杂度不会达到O(n * m)(n是 Arr1 的长度，m是 Arr2 的长度(。

遍历第二个数组并在第一个数组上使用indexOf或find，将为您提供最糟糕的m * n操作情况(如果 Arr2 中没有出现任何项目出现在 Arr1 中(。

因此，应首先创建 Arr2 的索引，以确保在使用 Arr1 时查找成本低廉。

困难的部分是确定如何为阵列编制索引以支持快速访问。一种方法是创建一个hash函数：

// Include the properties that determine equality in this hash function
const hash = ({ Name, Results }) => `${Name}|${Results}`;
console.log(
hash({ Name: "john.doe", Results: "Check", Timestamp: "-", Period: "Q2" })
);

使用此方法，可以通过一次遍历Arr2中的所有项目来创建{ string: Object }索引。

const hash = ({ Name, Results }) => `${Name}|${Results}`;
const arr2 = [
{ Name: "john", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "jane", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "aisha", Results: "Check", Timestamp: "-", Period: "Q2" }
];
console.log(
Object.fromEntries(arr2.map(x => [hash(x), x])) 
);

_{注意：根据 javascript 引擎的不同，最好使用for或while循环重写它。首先创建入口数组也会消耗一些内存。在这里，我只是想解释一下一般的方法。}

---

使用此索引，找到与 Arr2 元素的匹配项将(几乎？(具有恒定的时间复杂度。

const hash = ({ Name, Results }) => `${Name}|${Results}`;
const arr2 = [
{ Name: "john", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "jane", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "aisha", Results: "Check", Timestamp: "-", Period: "Q2" }
];
const arr1 = [
{ Name: "john", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "jane", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "aisha", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "robert", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "ellen", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "tin", Results: "Check", Timestamp: "-", Period: "Q2" }
];
const index = Object.fromEntries(arr2.map(x => [hash(x), x]));
const results = arr1.filter(p => index.hasOwnProperty(hash(p)));
console.log(`In both arrays: ${results.map(p => p.Name).join(", ")}`);

我不是计算机科学专业的毕业生，但我认为这将使您接近O(n + m)复杂性，这对于 2 x 450k 项目应该是可行的吗？

---

附言如果Object.fromEntries、map并且filter减慢速度，您可以重写为：

const arr2 = [
{ Name: "john", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "jane", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "aisha", Results: "Check", Timestamp: "-", Period: "Q2" }
];
const arr1 = [
{ Name: "john", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "jane", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "aisha", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "robert", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "ellen", Results: "Check", Timestamp: "-", Period: "Q2" },
{ Name: "tin", Results: "Check", Timestamp: "-", Period: "Q2" }
];
const index = {};
for (let i = 0; i < arr2.length; i += 1) {
const item = arr2[i];
index[`${item.Name}|${item.Results}`] = item;
}
const results = [];
for (let i = 0; i < arr1.length; i += 1) {
const item = arr1[i];
const match = index[`${item.Name}|${item.Results}`];
if (match) {
results.push(match);
}
}
console.log(`In both arrays: ${results.map(p => p.Name).join(", ")}`);