Javascript从Array中删除Object的最快方法

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中,以便下次加载或刷新页面时,执行最有效的方法:从数组中删除对象.

UPDATE

过滤器实验的片段

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

Answer 1

您需要迭代数组以查找单个项目的任何解决方案似乎表明您正在使用的数据结构存在问题.您可能应该将它们存储在一个对象中,而不是将对象存储在数字索引的数组中,其中键是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).

Answer 2

现有的答案已经为减少底层问题的运行时复杂性提供了很好的解决方案。

但是我也想简短地回答原始问题，因为这是在谷歌搜索如何以最有效的方式从数组中删除时的第一页。

如果不保持顺序，则按索引删除的最快方法是通过将最后一个元素分配给要删除的索引并从数组中弹出来进行删除，因为这具有O（1）运行时复杂性。

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

通过维护顺序，按索引删除的最快方法是在适当的地方移动：

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

    this.pop();
}

我创建了一个JS perf片段来对不同的功能进行基准测试：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

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);
});