JavaScript中从数组中删除对象的最快方法

Question

在一个追求速度的应用上工作，数组很大，且其中包含的对象也很多。

我尝试过grep 和 filter，但没有看到显著的速度差异，变化范围为+-5ms，我还尝试了通过循环数组并使用.splice(i,1);（结果相同）。

我的机器速度很快，如果它在快速的机器上始终需要大约相同的时间，那么这是否意味着它在旧的机器上需要大约相同的时间？

有没有更快的方法从数组中删除对象？

想要做的事情像这样：

var filterTime = performance.now();
doStuff1();
var filterTimeEnd = performance.now();

var grepTime = performance.now();
doStuff2();
var grepTimeEnd = performance.now();

然后将差异存储在cookie中，所以下次加载或刷新页面时，可以执行最有效的方式：从数组中移除对象。

更新

过滤器实验片段

      companyMasters = companyMasters.filter(function (obj) {
      return obj.masterId != CompanyObj.masterId;
      });

- Jack

---

你大概会删除多少个元素与数组大小成比例？ - twinlakes

如果你正在使用grep和filter，这里的排列组合比仅仅从数组中删除一个对象要多。你应该将你的用例放入http://jsperf.com进行测试，并在多台机器上测试。 - CodingIntrigue

@twinlakes 我正在从数组中删除一个对象，长度小于10,000，但它可能会变得非常非常大。 - Jack

你是要从数组中仅删除一个项目，还是每次删除一个项目？是什么决定了应该删除哪个项目？ - Guffa

最快遍历数组的方法是使用循环：https://dev59.com/mG435IYBdhLWcg3wjwzS - garryp

Answer 1

现有答案已经提供了降低底层问题运行时复杂度的好方法。

然而，我也想简要回答原始问题，因为这是谷歌搜索如何以最高效的方式从数组中删除的第一页。

不保持顺序 按索引删除的最快方法是将最后一个元素分配到要删除的索引并从数组中弹出，因为它具有O(1)的运行时复杂度。

Array.prototype.mySwapDelete = function arrayMySwapDelete (index) {
    this[index] = this[this.length - 1];
    this.pop();
}

保持有序的情况下，最快的按照索引删除的方法是就地移动：

Translated content:

保持有序的情况下，最快的按照索引删除的方法是就地移动：

Array.prototype.myShiftDelete = function arrayMyShiftDelete (index) {
    var stop = this.length - 1;
    while (index < stop) {
        this[index] = this[++index];
    }

    this.pop();
}

我创建了一个JS性能片段来对不同函数进行基准测试：https://jsperf.com/array-remove-by-index

如果想要筛选，使用原地过滤和移位要比调用本地的.filter()函数快得多，因为后者会分配一个新数组。这种原地过滤还可以维护顺序:

Array.prototype.myShiftFilter = function arrayMyShiftFilter (predicate) {
    let i, j;

    for (i = 0, j = 0; i < this.length; ++i) {
        if (predicate(this[i])) {
            this[j] = this[i];
            ++j;
        }
    }

    while (j < this.length) {
        this.pop();
    }
}

另请参考JS Perf代码段进行基准测试：https://jsperf.com/array-filter-in-place

- Maximilian Schier

---

我的循环加速了400%。 - wandergis

这个一行代码的意思是：将数组中最后一个元素弹出并赋值给指定索引位置。 - Kalabasa

@Kalabasa 对于长度为1的数组不起作用，检查该情况会产生可比较的代码复杂性，同时引入分支。 - Maximilian Schier

let list2 = [1, 2, 3]; let itemToRemoveIndex2 = 1;list2[itemToRemoveIndex2] = list2[this.length - 1]; list2.pop(); console.log(list2); 输出结果为 (2) [1, undefined] - Tom Smykowski

@TomaszSmykowski 是的，使用未定义的值索引list2会返回undefined，您可能想要使用list2.length进行索引。 - Maximilian Schier

这样做会更好。对于处理不可变数组的人，可以使用 Array.from()。但是这仍然非常快。 - Jack

Answer 2

任何需要迭代数组以查找单个项的解决方案都表明您正在使用的数据结构存在问题。建议您不要将对象存储在数字索引数组中，而是应该将它们存储在一个对象中，其中键是您将要进行查找的 masterId 值。如果由于某种其他原因需要将对象保留在数字索引数组中，您可以考虑构建一个单独的对象，将 masterId 值映射到主数组中对象所驻留的索引位置。

因此，不要像这样：

[
    {
        masterId: 'foo',
        ...
    },
    {
        masterId: 'bar',
        ...
    },
    ...
]

你可以像这样构建你的数据结构:

你需要构建你的数据结构如下:

{
    foo: {
        masterId: 'foo',
        ...
    },
    bar: {
        masterId: 'bar',
        ...
    },
    ...
}

这将使您的代码看起来像这样：

var needle = CompanyObj.masterId;
// delete object set for 'needle' property
delete companyMaster[needle];

这样可以使您拥有一个时间复杂度为O(1)的操作，而不是O(n)。

- Mike Brant

---

不幸的是，我必须将数字索引数组保留在另一侧：“构建一个单独的对象，在其中将masterId值映射到索引”并不是一个坏主意。 - Jack

@Jack，除非你能在构建数组的同时构建地图，否则你真的需要考虑是否需要单独创建一个地图。首先，你必须循环数组来构建地图（一个O(n)操作）。如果你只需要从数组中删除一个项目，那么你不会获得太多价值。但是，如果你需要删除多个值，你可能仍然会看到好处。无论如何，如果你需要循环数组进行查找，你应该在找到匹配项时内置一个break，这样你就不必循环整个数组了。 - Mike Brant

如果数组是绝对必要的，我也会有一个像Mike Brant展示的地图对象。除了id之外，这些对象还可以有一个索引，显示您如何快速到达并拼接出数组中的masterId。但是，然后你就需要更新所有映射的索引引用，以便于删除后面的数字。最终，是的...这就是数据库存在的原因，即使是JavaScript类型的数据库；以更可访问的方式存储东西。您的数组结构将会导致问题。把这个信息带给那些强制执行它的人。 - Katana314

@Jack，实际上，进一步思考映射方法，我认为你不会像我最初想的那样从中获得太多好处。如果你从数组中删除项目，这意味着你需要在每次删除更改映射到新索引值之后更新映射对象（因为这些值会随着删除而改变）。这将需要对映射进行迭代，因此不会获得太大的好处。因此，即使你必须以数组形式获取输入，你最好还是从数组构造我答案中提到的对象，然后丢弃数组。 - Mike Brant

@MikeBrant 是的，创建一个地图只会浪费时间，构建对象并丢弃数组会少很多麻烦。Katana314说，使用数据库可能比期望用户机器处理更快，更稳定，也许是mongoDB。 - Jack

Answer 3

不要反复循环数组以逐个删除项目，而是构建一个映射表，您可以使用它来一次性过滤掉所有项目：

var map = {};
for (var i = 0; i < itemsToRemove.length; i++) {
  map[itemsToRemove[i]] = 1;
}

companyMasters = companyMasters.filter(function (obj) {
  return !(obj.masterId in map);
});

- Guffa

---

这是对原帖中代码的显著改进，因为至少你只循环了一次数组，删除了所有需要被移除的项。单独为每个要删除的项进行循环将会非常棘手。 - Mike Brant