More efficient way to remove an element from an array in Actionscript 3

Question

I have an array of objects. Each object has a property called name. I want to efficiently remove an object with a particular name from the array. Is this the BEST way?

  private function RemoveSpoke(Name:String):void {
    var Temp:Array=new Array;
    for each (var S:Object in Spokes) {
      if (S.Name!=Name) {
        Temp.push(S);
      }
    }
    Spokes=Temp;
  }

Solution 1

If you are willing to spend some memory on a lookup table this will be pretty fast:

private function remove( data:Array, objectTable:Object, name:String):void {
var index:int = data.indexOf( objectTable[name] );
objectTable[name] = null;
data.splice( index, 1 );
}

The test for this looks like this:

private function test():void{

var lookup:Object = {};
var Spokes:Array = [];
for ( var i:int = 0; i < 1000; i++ )
{
    var obj:Object = { name: (Math.random()*0xffffff).toString(16), someOtherProperty:"blah" };
    if ( lookup[ obj.name ] == null )
    {
        lookup[ obj.name ] = obj;
        Spokes.push( obj );
    }
}

var t:int = getTimer();
for ( var i:int = 0; i < 500; i++ )
{
    var test:Object = Spokes[int(Math.random()*Spokes.length)];
    remove(Spokes,lookup,test.name)
}
trace( getTimer() - t );

}

Solution 2

myArray.splice(myArray.indexOf(myInstance), 1);

Solution 3

The fastest way will be this:

function remove(array: Array, name: String): void {
  var n: int = array.length
  while(--n > -1) {
    if(name == array[n].name) {
      array.splice(n, 1)
      return
    }
   }
}

remove([{name: "hi"}], "hi")

You can also remove the return statement if you want to get rid of all alements that match the given predicate.

Solution 4

I don't have data to back it up but my guess is that array.filter might be the fastest.

Solution 5

In general you should prefer the old for-loop over "for each" and "for each in" and use Vector if your elements are of the same type. If performance is really important you should consider using a linked list.

Check out Grant Skinners slides http://gskinner.com/talks/quick/ and Jackson Dunstan's Blog for more infos about optimization.

View more solutions

Comments

[user7740901]

Joa! You rock. But will Apparat be able to make it even faster? :)

[Quasimondo]

I allowed myself to compare your "fastest" against mine and come with bad news: removing 500 elements from a 1000 elements array - yours 34 ms, mine 4ms ;-)

[Quasimondo]

FYI ArrayCollection is only available in Flex

[Quasimondo]

If you mean something like this: var filterName:String = "something"; Spokes = Spokes.filter(function( element:*, index:int, arr:Array):Boolean { return (element.name != filterName);}); then I must disappoint you.It's about 5x slower than Joa's and almost 30x slower than mine.

[user7740901]

Haha. You guys cheat! ;) Is array.filter at least the fastest for the loop / iterator based methods?

[Quasimondo]

One important thing about this solution: it will only work if each "name" is unique. If there are multiple objects with the same name the lookup table will fail, at least if it is built like this.

[mga]

interesting... so you basically have two lists with duplicate data... in general would it be better to just use lookup tables and dispense with arrays for these situations? does this work just because the object has a name property or the indexOf method searches in every property value of the object?

[Quasimondo]

Yes, if you do not need the array for other purposes (like sorting or accessing elements by index) in this case you could just use the lookup table. indexOf finds instances of an object. In this case it does not use "name" at all for the comparison. The name is used as the hash in the lookup table.

[Quasimondo]

It looks like the formatting removed the type of your vector, but I guess it's "Object". I tested it quickly and at least for me using Vector in this case is actually slower. I think if you want to profit from the speed of Vector you should also use a real type and not "Object".

[Robusto]

@Quasimondo: FYI Flex is one of the tags on the question.

[Quasimondo]

Oh true, I totally missed that one.

[Juan Pablo Califano]

+1. This is clever. On an unrelated and uncalled for rant, you've got to love how people bitch about Object being slow, when it's often the fastest option if used wisely and if it fits in the solution. That said, I'd personally go with just one array, a linear search and splice (and no pre/post increment/decrement trickery in the loop) unless there is an actual and real need for this extra speed.

[sharvey]

What is the point of wrapping it in the ArrayCollection? you could just splice the array directly. Or am I missing something?

[reelfernandes]

Thanks Quasi. Did you test using my function? It has an added conditional ( hasOwnProperty ) that would slow it but make sense if you're not sure the object will have the property. To make it faster remove that. But the user asked about efficiency, and this function speaks to that in terms of reusability.

[Quasimondo]

I tested it with Joa's proposal, so the hasOwnProperty was not the issue here.