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.

Decamp

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

Exothermic

splice() is indeed the way to go, but keep in mind that removing things in the middle will be slow with large arrays since flash will "move up" the later entries to fill the gap. – Albeit

Also keep in mind that removing things in the middle of an array while running through it will wreak havoc unless you're running backwards. – Julejulee

For anyone who cares about the value of the specific entry being removed, remember that splice returns an array, so you would need array.splice(5, 1)[0]; – Industrials

Answer 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.)

Brough

That is really clever. Ridiculously faster than splice: jsperf.com/remove-element-splice-vs-move-and-pop – Cover

+1, how about a one-liner: array[index] = array.pop( ) or even array[index] = array[array.length-- -1] – Goldberg

@copy, yes correct, i saw that afterwards, however it is one-liner under the condition that there are more than one lements – Goldberg

@copy here a correct one: (array.length > 1) && (array[index] = array.pop( )) || array.pop() – Goldberg

@Cover Is it still faster than splice? – Amalamalbena

@Amalamalbena yes it will probably always be. (Oh the things I found clever back then...) – Cover

"#MaiaVictor Is it still faster than splice?" @Amalamalbena So the weird thing about compilers (well, interpreters. Well...) is that if there's a smarter way to handle a process, they'll eventually use it. That said, one poorly-written jsbench test tells me .pop (this solution) is still almost twice as fast (?) as splicing. ;^) – Hairsplitting

Answer 3

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

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

Jairia

Answer 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/

Hirudin

Answer 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];

Euphony