Array.prototype.filter() 的就地替代方法是什么

IT技术 javascript functional-programming
2021-02-26 02:39:28

我有一个数组,我想从中删除一些元素。我不能使用Array.prototype.filter(),因为我想就地修改数组(因为它节省了内存分配,而且对我来说更重要的是,使我的用例中的代码更简单)。是否有filter我可以使用的就地替代方案,也许类似于如何Array.prototype.forEach()将其用作就地变体Array.prototype.map()

编辑:应要求提供的最小示例:

function someCallback(array) {
  // do some stuff
  array.filterInPlace(function(elem) {
    var result = /* some logic */
    return result;
  })
  // do some more stuff
}
6个回答

是否有就地替代过滤器

不,但是自己编写并不难。这是一种挤出所有不符合条件的值的方法。

function filterInPlace(a, condition) {
  let i = 0, j = 0;

  while (i < a.length) {
    const val = a[i];
    if (condition(val, i, a)) a[j++] = val;
    i++;
  }

  a.length = j;
  return a;
}

condition设计为具有与传递给 的回调相同的签名Array#filter,即(value, index, array)为了与 完全兼容Array#filter,您还可以接受第四个thisArg参数。

使用 forEach

使用forEach有一个小优势,它会跳过空槽。这个版本:

  • 用空槽压缩数组
  • 工具 thisArg
  • 跳过分配,如果我们还没有遇到失败的元素

function filterInPlace(a, condition, thisArg) {
  let j = 0;

  a.forEach((e, i) => { 
    if (condition.call(thisArg, e, i, a)) {
      if (i!==j) a[j] = e; 
      j++;
    }
  });

  a.length = j;
  return a;
}

a = [ 1,, 3 ];
document.write('<br>[',a,']');

filterInPlace(a, x=>true);
document.write('<br>[',a,'] compaction when nothing changed');

b = [ 1,,3,,5 ];
document.write('<br>[',b,']');

filterInPlace(b, x=>x!==5);
document.write('<br>[',b,'] with 5 removed');

此答案使用与如何使用 Javascript 删除数组中的所有奇数的最高投票答案相同的算法
2021-04-26 02:39:28
编辑以更正此答案。filterInPlace() 截断了带有孔的数组中的附加值。 看问题显而易见的修复也失败了。然而,这个变体似乎有效。
2021-05-05 02:39:28
很好的触摸只调整阵列大小一次。我喜欢。我实际上从不知道您可以为该length属性赋值以产生效果。
2021-05-19 02:39:28

您可以使用以下内容:

array.splice(0, array.length,...array.filter(/*YOUR FUNCTION HERE*/))

解释:

  • 拼接动作到位
  • 第一个参数意味着我们从数组的开头开始
  • 第二种意味着我们删除整个数组
  • 第三意味着我们用它的过滤副本替换它
  • ... 是扩展运算符(仅限 ES6)并将数组的每个成员更改为单独的参数
不过,它并没有就地进行过滤……它在单独的数组中进行过滤,清空原始文件,然后将过滤器结果复制到清空的原始文件中。不会像 OP 那样节省内存分配。
2021-05-02 02:39:28
它仍然很有用,因为它保留了对数组对象的原始引用,而不是更改对其他数组的引用。
2021-05-07 02:39:28

你可以使用什么

  • Array#filter 返回具有相同元素的数组,但不一定是所有元素。
  • Array#map 为每个循环返回一些东西,结果是一个与源数组长度相同的数组。
  • Array#forEach 什么都不返回,但每个元素都被处理,就像上面一样。
  • Array#reduce 返回你想要的任何东西。
  • Array#some/Array#every返回一个布尔值。

但是上面的任何内容都没有在原位改变原始数组的长度问题。

我建议使用 while 循环,从最后一个元素开始并将拼接应用于要删除的元素。

这使索引保持有效并允许为每个循环递减。

例子:

var array = [0, 1, 2, 3, 4, 5],
    i = array.length;

while (i--) {
    if (array[i] % 2) {
        array.splice(i, 1);
    }
}
console.log(array);

我的推理是否正确,使用这样的array.splice具有运行时 O(array.length^2),并且如果我删除了数组的大部分,那么速度很慢?我不需要挤出每一盎司的性能,但这对我来说太慢了。
2021-04-23 02:39:28
感谢您的努力,但我更喜欢 torazaburo 的 O(n) 解决方案。
2021-05-03 02:39:28
Perseids,你为什么假设 O(array.length^2)?我认为这是最好的解决方案,既因为它有效,就地删除元素,而且因为 .splice 与反应数组一起工作,这非常有用。
2021-05-04 02:39:28
这与filter(),forEach()和 有map()什么相似之处
2021-05-15 02:39:28
虽然我会使用过滤器,但由于原位需要,您必须对您的要求采取一些缺点。
2021-05-17 02:39:28

如果您能够添加第三方库,请查看lodash.remove

predicate = function(element) {
  return element == "to remove"
}
lodash.remove(array, predicate)

当前选择的答案非常有效。但是,我希望这个函数成为 Array 原型的一部分。

Array.prototype.filterInPlace = function(condition, thisArg) {
    let j = 0;

    this.forEach((el, index) => {
        if (condition.call(thisArg, el, index, this)) {
            if (index !== j) {
                this[j] = el;
            }
            j++;
        }
    })

    this.length = j;
    return this;
}

有了这个,我可以像这样调用函数:

const arr = [1, 2, 3, 4];
arr.filterInPlace(x => x > 2);
// [1, 2]

我只是将它保存在一个名为 Array.js 的文件中,并在需要时使用它。