时间戳

首页 > 解决方案 > 在 Javascript 中比较两个对象数组与文字值的更快方法

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

问题描述

  1. 具有字面值的对象数组意味着，它是一个数组，它的每个元素都是一个对象，而这样的对象的值都是字面量（所以它不会是嵌套对象，对象内的数组等），例如，它可：
[ { name: 'Bob', age: 20, isMale: true }, { name: 'Alice', age: 19, isMale: false}, ... ]
  1. 比较的意思是，我们需要区分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 个属性值。像这样：

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

我自己测试过，使用我的方法将花费：

  1. ~10 秒完成 <= 太慢了
  2. 由于计算量大，浏览器将冻结 <= 主要问题！

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

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

标签： javascriptalgorithmlodash

解决方案

将每个对象与每个对象进行比较会导致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))即使对于数百万个项目也足够好。

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

推荐阅读