javascript - 在 Javascript 中比较两个对象数组与文字值的更快方法

Question

1. Array of Objects with Literal Values 的意思是，它是一个数组，它的每个元素都是一个对象，而这样的对象的值都是文字(所以它不会'不是嵌套对象、对象内部数组等)，例如，它可以是:

[ { name: 'Bob', age: 20, isMale: true }, { name: 'Alice', age: 19, isMale: false}, ... ]

1. Compare的意思是，我们需要区分added和removed元素，例如:

const original = [ { name: 'Bob', age: 20, isMale: true }, { name: 'Alice', age: 19, isMale: false} ];
const modified = [ { name: 'Alice', age: 19, isMale: false}, { name: 'Jay', age: 21, isMale: true } ];

// then added = [{ name: 'Jay', age: 21, isMale: true }]
// and removed = [{ name: 'Bob', age: 20, isMale: true }]

我的方法:使用 lodash 的 differenceWith 和 isEqual 来实现，例如:

const original = [ { name: 'Bob', age: 20, isMale: true }, { name: 'Alice', age: 19, isMale: false} ];
const modified = [ { name: 'Alice', age: 19, isMale: false}, { name: 'Jay', age: 21, isMale: true } ];

const removed = _.differenceWith(original, modified, _.isEqual);
const added = _.differenceWith(modified, original, _.isEqual);

^ 但是，它不够快!! 我有两个数组的样本，每个数组包含 10K+ 个对象，而每个对象都有 3 个具有 lietal 值的属性。像这样:

[{lat: 123.321, long: 234.432, radius: 100}, ....]         // 10K+ elements

我自己测试过，使用我的方法会花费:

1. ~10 秒完成 <= 太慢
2. 浏览器会因为繁重的计算而死机 <= 主要问题!

现在的问题是，您能否提供一种更快、更优雅的方法来比较此类样本？

我的一个猜测是我可以通过将 isEqual 替换为其他内容来改进，但不确定在这种情况下是否有帮助。

Answer 1

将每个对象与每个对象进行比较将导致 O(n^2) 问题，正如您所注意到的那样，复杂性增长非常快，然后是 10k 个对象(这在计算机世界中并不多) 几乎无法处理。

然而，有更简单的方法来完成这个。

预处理

1. 按名称对两个数组进行排序，这需要 O(n*log(n))
2. 从 0 开始为每个数组设置两个索引，我们称它为 i 和 j

处理

1. 比较 original[i] 和 modified[j]
中的名称
2. 如果相同，就是i++和j++
3. 如果不同，则在字符串比较中检查哪个“更低”(比如 Bob 比 Cathrine 低，因为它以 B 开头)
4. 如果original[i]较低，则将其添加到removed和i++
5. 如果modified[j]较低，则将其添加到added和j++
6. 重复直到处理完两个数组

最昂贵的部分是排序，其他一切都在 O(n) 时间内完成，因此整体复杂度将为 O(n*log(n))即使对于数百万个项目，这也足够了。

注意:如果您还需要比较年龄或性别，而不仅仅是姓名，则需要更新以上内容，按多个字段排序，然后按多个字段进行比较)