数组慢速元素删除

Question

数组慢速元素删除

javascriptarraysperformance

4

我有一个数组，想要从头部删除N个元素。

比如说，这个包含浮点数的数组有100万个元素，我想把前面的500K去掉。我有两种方法，一种是在循环中连续调用500K次shift函数，另一种是调用splice(0,500000)。

第一种方法非常慢，不可取。第二种方法也较慢，因为splice会将被移除的部分作为新数组返回（它只是分配了500K个浮点数并将其丢掉）。

在我的应用程序中，我需要处理大型矩阵，并且不幸的是，通过splice删除元素对我来说太慢了。是否有更快的方法来实现这一操作？

- dev1223

2个回答

1

Immutable.js通过结构共享来解决这个问题。它不像splice那样复制条目，而是返回数组中包含部分的引用。您需要将数组移动到Immutable.js数据结构中，然后调用不可变操作splice。

- Daniel Schmidt

这有两个问题。第一个是，高效的不可变结构使用递归结构（链接节点），导致访问时间缓慢（我需要非常快的访问时间）。其次，我不能将其移动，因为这将再次复制1M个元素。 - dev1223

@T.J.Crowder: 输入了回车键而不是按下Shift+Enter。 - dev1223

你确定吗？我认为在JavaScript中这种链接是不可能的，数据结构是用另一种方式实现的。据我所知。 - Daniel Schmidt

只要语言有引用，就可以实现。不可变的结构不能是数组或类似数组的结构，因为每次更改都只能通过新副本完成，而完整数组的新副本非常慢。如果使用一些基于节点的结构（递归），则此副本非常便宜，因为您可以将新副本链接到原始结构的部分。您只需要从根节点复制到更改的节点，其他所有分支都会链接回来（列表仅退化为一个分支的树）。尝试在JS中实现一些不可变的搜索树。 - dev1223

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- T.J. Crowder · Accepted Answer

我认为Array#slice的速度应该至少与这两个选项之一相同，甚至更快。虽然这意味着需要暂时分配重复的内存，但是1M个数字只占用大约64MB的内存（假设JavaScript引擎已经能够在底层使用真正的数组），因此在释放原始的64MB之前，暂时保留原始的64MB以及要保留的32MB似乎相当便宜：

array = array.slice(500000);

这样做的好处是它不会强制JavaScript引擎在内部使用对象而不是数组。(您正在执行的其他操作可能会导致此问题，但是...)

您已经说过您正在使用浮点数，您可以考虑使用Float64Array而不是未定义类型的数组。这限制了您可以执行的操作，但确保您不会得到未优化的数组。当您从数组中删除条目时，您可能会得到未优化的数组，其访问时间明显较慢，因为它们最终成为具有命名属性而不是偏移访问的对象。(一个好的JavaScript引擎将尽可能地保持它们的优化;使用类型化数组将有助于防止您破坏其优化。)

这个（匆忙编写且很可能有缺陷的）NodeJS测试表明，splice比slice慢60%至95%，而V8在类型化数组的情况下可以很好地保持数组的优化，因为结果与未定义类型的数组的结果几乎相同：

"use strict";
let sliceStats = createStats();
let sliceTypedStats = createStats();
let spliceStats = createStats();
for (let c = 0; c < 100; ++c) {
    if (test(buildUntyped, sliceStats, testSlice).length != 500000) throw new Error("1");
    if (test(buildTyped, sliceTypedStats, testSlice).length != 500000) throw new Error("2");
    if (test(buildUntyped, spliceStats, testSplice).length != 500000) throw new Error("3");
    console.log(c);
}
console.log("slice     ", avg(sliceStats.sum, sliceStats.count));
console.log("sliceTyped", avg(sliceTypedStats.sum, sliceTypedStats.count));
console.log("splice    ", avg(spliceStats.sum, spliceStats.count));

function avg(sum, count) {
    return (sum / count).toFixed(3);
}

function createStats() {
    return {
        count: 0,
        sum:   0
    };
}
function buildUntyped() {
    let a = [];
    for (let n = 0; n < 1000000; ++n) {
        a[n] = Math.random();
    }
    return a;
}

function buildTyped() {
    let a = new Float64Array(1000000);
    for (let n = 0; n < 1000000; ++n) {
        a[n] = Math.random();
    }
    return a;
}

function test(build, stats, f) {
    let a;
    let ignore = 0;
    let start = Date.now();
    for (let i = 0; i < 10; ++i) {
        let s = Date.now();
        a = build();
        ignore += Date.now() - s;
        a = f(a);
    }
    stats.sum += Date.now() - start - ignore;
    ++stats.count;
    return a;
}

function testSlice(a) {
    return a.slice(500000);
}
function testSplice(a) {
    a.splice(0, 500000);
    return a;
}