Fastest way to delete one entry from the middle of Array()

Question

What is the fastest way to delete one specific entry from the middle of Array()

Array is large one having Strings.

I dont want just to set Array[5] = null, but instead array size should be reduced by one and array[5] should have content of array[6] etc.

Solution 1

Don't have any benchmarks to support this, but one would assume that the native Array.splice method would be the fastest...

So, to remove the entry at index 5:

array.splice(5, 1);

Solution 2

If you don't care about the order of the items in the array (but just want it to get 1 shorter) you can copy the last element of the array to the index to be deleted, then pop the last element off.

array[index] = array[array.length-1];
array.pop();

I would guess this is faster, CPU-time-wise, if you can get away with reordering the array.

EDIT: You should benchmark for your specific case; I recently did this, and it was faster to just splice. (Presumably because Chrome is not actually storing the array as a single continuous buffer.)

Solution 3

Array.splice() "adds elements to and removes elements from an array":

myArr.splice(indexToRemove, 1); // only removing one index, thus the 1

Solution 4

I tested Array.prototype.splice() and found that it's very slow on large arrays.

A much faster way of removing elements is to copy the ones you wish to keep to a new array, while skipping the ones you want to remove. After you've finished copying, you simply override the old array with the new one.

In my test I removed every other element from an array containing 100.000 items. The test compared Array.prototype.splice() to other methods. Here are the results:

855 ms = splice
  7 ms = manual copying without preserving the original array
 14 ms = manual copying with preserving the original array

Here's the code for the last method:

var arrB = [],
    i=varA.length,
    j=0;

// copy even items to a new array
while(i > 0) {
    i-=2; // skip two elements
    arrB[j++] = arrA[i];
}

// clear the old array
arrA.splice(0, arrA.length);

// copy values back to the old array
// array is preserved (references to the array don't need to be updated)
arrA.push.apply(arrA, arrB);

The test in action can be found on jsFiddle: http://jsfiddle.net/sansegot/eXvgb/3/

The results are much different if you only need to remove a few items - in such cases Array.prototype.splice() is faster (although the difference is not so large)! Only if you need to call splice() many times it's worth it to implement custom algorithm. The second test, in which a limited number of elements are to be removed can be found here: http://jsfiddle.net/sansegot/ZeEFJ/1/

Solution 5

Depending on your case, you may consider using a Dictionary instead of an Array if you want to prioritize the performance.

var dict:Dictionary = new Dictionary();

// The following value/key set should be customized so you can 
// get use of them in your specific case.

dict[item1] = item1;
dict[item2] = item2;

...

delete dict[item1];

View more solutions