JavaScript 性能 : Loop and indexOf with large Arrays

Question

我目前遇到 JavaScript 操作性能问题。

我想清理一个对象数组 (aEmployees)，以查找那些 ID 已在数组 aInvited 中的对象。或不在 aInvitationAllowed 中数组:

var iLength = aEmployees.length - 1;
for (var i = iLength; i >= 0; --i) {
   if (aInvited.indexOf(aEmployees[i].id) !== -1 || aInvitationAllowed.indexOf(aEmployees[i].id) === -1) {
      aEmployees.splice(i, 1);
   }
}

您可以想象我有 Employee 对象 (aEmployees)。我还有已受邀参加事件的员工 ID 列表 (aInvited) 和允许受邀参加事件的员工 ID 列表 (aInvitationAllowed)。我希望所有员工都能被邀请参加该事件。

问题出在 indexOf 的行上查询。我必须假设数组有很多条目(约 100,000 个条目)。那么循环可能需要一段时间。

所以我的问题是:如何使循环更快？ indexOf 是否有更快的替代方案？

感谢您的提示!

Answer 1

考虑使用Set来进行比较。 Set.has 是一个 O(1) 操作，而 indexOf 是一个 O(n) 操作，减少了总体计算复杂度为 O(n) 而不是 O(n^2):

const aInvitedSet = new Set(aInvited);
const aAllowedSet = new Set(aAllowed);

const iLength = aEmployees.length - 1;
for (let i = iLength; i >= 0; --i) {
  const { id } = aEmployees[i];
  if (aInvitedSet.has(id) || !aAllowedSet.has(id)) {
    aEmployees.splice(i, 1);
  }
}

此外，splice 速度很慢。除非您必须改变现有数组，否则您可能会考虑.push到一个新数组(看起来是faster而不是Array.prototype。过滤器):

const aInvitedSet = new Set(aInvited);
const aAllowedSet = new Set(aAllowed);
const newArr = [];

const iLength = aEmployees.length;
for (let i = 0; i < iLength; i++) {
  const employee = aEmployees[i];
  const { id } = employee;
  if (!aInvitedSet.has(id) && aAllowedSet.has(id)) {
    newArr.push(employee);
  }
}