在数组之间高效地传输元素

Question

我有几个 JavaScript 数组，每个数组都包含指向对象的指针列表。当一个对象满足特定条件时，它的指针必须从它当前包含的数组中移除并放入不同的数组中。

我目前（天真的）解决方案是 splice 退出数组元素并 concat 将它们赋值到它们正在进入的数组中。这是一种缓慢的方法，并且随着时间的推移似乎会产生内存碎片。

任何人都可以就更好的方法提供建议（一般的或特定于 JS 的）吗？

演示代码：

// Definitions
TestObject = function() {
    this.shouldSwitch = function() {
        return(Math.random() > 0.9);
    }
}

A = [];
B = [];

while(A.length < 500) {
    A.push(new TestObject());
}

// Transfer loop
doTransfers = function() {
    var A_pending = [];
    var B_pending = [];
    for(var i = 0; i < A.length; i++) {
        if(A[i].shouldSwitch()) {
            B_pending.push(A[i]);
            A.splice(i,1);
            i--;
        }
    }
    for(var i = 0; i < B.length; i++) {
        if(B[i].shouldSwitch()) {
            A_pending.push(B[i]);
            B.splice(i,1);
            i--;
        }
    }

    A = A.concat(A_pending);
    B = B.concat(B_pending);
}

setInterval(doTransfers,10);

谢谢！

Answer 1

splice 对循环性能非常有害。但是您似乎不需要对输入数组进行任何更改 - 您正在创建新数组并覆盖以前的值。

随心所欲

function doTransfers() {
    var A_pending = [];
    var B2_pending = [];
    for (var i = 0; i < A.length; i++) {
        if (A[i].shouldSwitch())
            B_pending.push(A[i]);
        else
            A_pending.push(A[i]);
    }
    var B1_pending = [];
    for (var i = 0; i < B.length; i++) {
        if (B[i].shouldSwitch())
            A_pending.push(B[i]);
        else
            B1_pending.push(B[i]);
    }

    A = A_pending;
    B = B1_pending.concat(B2_pending);
}

Answer 2

对于此问题的一种独立于语言的解决方案，当您将元素从一个连续序列（数组）转移到另一个序列（数组）时，它不会将元素附加到新数组的后面，这将成为瓶颈（常数时间复杂度），它将是从现有容器中间移除元素（线性时间复杂度）。

因此，您可以获得的最大好处是用仍然使用缓存友好的连续数组表示的恒定时间操作替换从数组中间删除的线性时间操作。

执行此操作的最简单方法之一是简单地创建两个新数组而不是一个：一个用于附加要保留的元素的新数组和一个用于附加要传输的元素的新数组。完成后，您可以将要保留（而不是转移）的新元素数组替换为您拥有的旧数组。

在这种情况下，我们将线性时间移除从一个容器的中间交换为一个新容器的后面的摊销常数时间插入。虽然插入到容器末尾的重新分配在最坏情况下的复杂度仍然为 O(N)，但这种情况发生的频率足够低，而且通常仍然比每次为平均复杂度为 O(N) 的操作付费要好得多您通过不断从中间移除来转移单个元素。

解决这个问题的另一种方法可以更有效，特别是对于某些情况，比如非常小的数组，因为它只创建一个新数组，是这样的：

... 当你传输一个元素时，首先将它的一个副本（可能只是一个浅表副本）附加到新容器中。然后用旧容器后面的元素覆盖旧容器中该索引处的元素。现在只需弹出旧容器背面的元素即可。所以我们一推，一赋值，一弹出。

在这种情况下，我们使用单个赋值（store/move 指令）交换容器中间的线性时间移除和容器背面的恒定时间弹出（通常基本算术）。如果可以稍微改变旧数组中元素的顺序，这会非常有效，并且通常是一个被忽视的解决方案，用于将线性时间从数组中间移除到具有恒定时间复杂度的数组数组的后面。

在数组之间高效地传输元素

Efficiently transferring elements between arrays

javascript

arrays

optimization

memory-management

data-structures