Much faster Array.split() on all targets

[Samuel Batista]

A friend of mine recently introduced me to an interesting way of removing elements from an array. This only works when removing one element from an array:

if(index < arr.length - 1)

arr[index] = arr.pop();

else

arr.pop();

I ran the following test:

var testLen = 10000;

var arrSplice:Array<String> = new Array<String>();

var arrPop:Array<String> = new Array<String>();

for (i in 0 ... 10000)

{

arrSplice.push(cast(i));

arrPop.push(cast(i));

}

var timer = Lib.getTimer();

testLen = arrSplice.length;

while (testLen > 0)

{

arrSplice.splice(--testLen, 1);

}

trace("Splice test time: " + cast(Lib.getTimer() - timer) + "ms");

timer = Lib.getTimer();

testLen = arrPop.length;

while (arrPop.length > 0)

{

if(arrPop.length > 1)

arrPop[0] = arrPop.pop();

else

arrPop.pop();

}

trace("Pop test time: " + cast(Lib.getTimer() - timer) + "ms");

Results:

Flash

• arr.split = 45ms
• pop hack = 5ms

Neko

• arr.split = 5ms
• pop hack = 1ms

HXCPP

• arr.split = 1ms
• pop hack = 0ms

[Raoul Duke]

On Tue, Nov 20, 2012 at 2:38 PM, Samuel Batista <samba...@gmail.com> wrote:
> A friend of mine recently introduced me to an interesting way of removing
> elements from an array. This only works when removing one element from an
> array:

cool.

though worth explicitly stating that it only helps if you don't care
about ordering. :-)

[Samuel Batista]

Yes, it won't work on sorted arrays. Thanks for pointing it out!

[Luca]

Probably faster to just do:

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

to avoid the conditional branch.

[Justin Donaldson]

This is called "swap and pop" if you want to find other versions of it.  It's a good trick.

--
To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en