CODEWITHSUNDEEP
javascriptarraysoptimizationmemory-managementdata-structures
Mollusq
Mollusq

Reputation: 75

Efficiently transferring elements between arrays

I have several JavaScript arrays, each containing a list of pointers to objects. When an object meets a certain condition, its pointer must be removed from its current containing array and placed into a different array.

My current (naive) solution is to splice out the exiting array elements and concatenate them onto the array they are entering. This is a slow method and seems to fragment memory over time.

Can anyone offer advice (general or JS-specific) on a better way to do this?

Demonstration code:

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

Thanks!

Upvotes: 0

Views: 227

Answers (2)

user4842163
user4842163

Reputation:

For a language-independent kind of solution to this problem, when you're transferring elements from one contiguous sequence (array) to another, it's not appending elements to the back of the new array that's going to be bottlenecky (constant time complexity), it's going to be the removal of elements from the middle of your existing container (linear time complexity).

So the biggest benefit you can get is to replace that linear-time operation of removing from the middle of the array with a constant-time operation that still uses that cache-friendly, contiguous array representation.

One of the easiest ways to do this is to simply create two new arrays instead of one: a new array to append the elements you want to keep and a new array to append the elements you want to transfer. When you're done, you can swap out the new array of elements you want to keep (not transfer) with the old array you had.

In such a case, we're exchanging linear-time removals from the middle of a container with amortized constant-time insertions to the back of a new one. While insertion to the end of a container still has a worst-case complexity of O(N) for reallocations, it occurs infrequently enough and is still generally far better than paying for an operation that has an average complexity of O(N) every time you transfer a single element by constantly removing from the middle.

Another way to solve this problem that can be even more efficient, especially for certain cases like really small arrays since it only creates 1 new array, is this:

... when you transfer an element, first append a copy of it (possibly just a shallow copy) to the new container. Then overwrite the element at that index in the old container with the element from the back of the old container. Now simply pop off the element at the back of the old container. So we have one push, one assignment, and one pop.

In this case, we're exchanging a linear-time removal from the middle of a container with a single assignment (store/move instruction) and a constant-time pop from the back of the container (often basic arithmetic). This can work extremely well if the order of the elements in the old array can be shuffled around a little bit, and is often an overlooked solution for getting that linear-time removal from the middle of the array into one with constant-time complexity from the back of the array.

Upvotes: 1

Bergi
Bergi

Reputation: 664484

splice is pretty harmful for performance in a loop. But you don't seem to need mutations on the input arrays anyway - you are creating new ones and overwrite the previous values.

Just do

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

Upvotes: 0

Related Questions