[as3]This had me bugging for a long time.

17 posts

Flag Post

Hello everyone. For months i had one question in mind: what happens when we do this:

//a is an array
//b is true or false, depends on i
for (i = 0; i<a.length; i++)
{
if (b)
a.splice(i, 1);
}

Does it remove the element from array immediately? Or does it wait until the loop is finished? Will it make the loop skip some elements? I had been trying to avoid actions like above because i don’t know if what the result will be.

 
Flag Post

Splice will remove the element from the array immediately (ie. before the next iteration of the loop). So, yes, you will end up skipping elements if you do it like that. There’s a number of options: either decrement i each time an element is removed, run through the loop backwards, or reorder your loop each time you remove an element.

//Option 1
for(var i:int = 0;i<a.length;i++){
   if(b){
      a.splice(i,1);
      i--;
   }
}
//Option 2
for(var i:int = a.length-1;i>=0;i--){
   if(b){
      a.splice(i,1);
   }
}
//Option 3
for(var i:int = 0;i<a.length;i++){
   if(b){
      a[i] = a[a.length-1];
      i--;
      a.length--;
   }
}
 
Flag Post
Originally posted by a3lex33:

For months i had one question in mind: what happens when we do this:

How did you survive ? Seriously, when I obsess about a behavior question like this one for more than 30 minutes, I just drop everything, fire up FD and test it! I mean, you do have the tools and the answers right at your fingertips, what took “months”?

 
Flag Post

The fastest (apparently) way of iterating is the second of what feartehstickman provided. Sometimes the order matters, so you have to do play with the index.

 
Flag Post

for each & for each in loops

 
Flag Post
Originally posted by vesperbot:

The fastest (apparently) way of iterating is the second of what feartehstickman provided. Sometimes the order matters, so you have to do play with the index.

The third should be the fastest because it doesn’t use splice(), but that comes at the expense of order.
If you precompute the length of the array, apparently 1 is faster than 2 because of some caching or something that takes place (I don’t know, but I keep hearing it).
Originally posted by player_03:
Originally posted by Lucidius:

iterate backwards through vectors instead of forwards.

I don’t know about this one. In many cases, the machine will optimize for iterating forwards. That is, when you retrieve tempVector[3], it will also retrieve and cache tempVector[4], tempVector[5], and perhaps a few more. This won’t be any use if you iterate backwards, though.

If you’re worried about looking up tempVector.length every iteration, store it in a variable.

 
Flag Post

@fear what about Option 4 which is option 3 with backwards loop.

Write ALL the options! [missing graphic here]

 
Flag Post

It might have similar issues with caching as 2 and the benefit of it (that you don’t need to store length) is somewhat decreased by needing it for rearranging.

//Option 4
for(var i:int = a.length-1;i>=0;i--){
   if(b){
      a[i] = a[a.length-1];
      a.length--;
   }
}

Unless, of course, you can do this… (I don’t know if it’ll work or not, and I can’t test at the moment)

//Option 5
for(var i:int = a.length-1;i>=0;i--){
   if(b){
      a[i] = a[a.length--];
   }
}
 
Flag Post

You could always test it in your browser…

It shrinks the array length before accessing the element at the end.

 
Flag Post

I went ahead and tested these algorithms.

Benchmark: You are given a list that is 120 items long. 100 items are the string “yes” and 20 are the string “no”. (The exact criterion used is: i % 11 == 0 || i % 13 == 0.) The goal is to remove all “no” strings.

Displayed below is the time it takes to complete 10000 trials. Each trial includes the overhead of creating a new copy of the source list, plus the (much smaller) overhead of ensuring that the list ended up with a length of exactly 100.

Option 1: 0.282s
Option 2: 0.281s
Option 3: 0.0501s
Option 4: 0.0501s

Option 5: [Skipped because it doesn’t work]

Originally posted by UnknownGuardian:

Write ALL the options!

Ok then:

Option 6: 0.0760s
Option 7: 0.0768s

Code for option 6:

for(var i:int = 0; i < a.length; i++){
    if(b){
        a[i] = null;
    }
}
var remainingCount:int = 0;
for(var i:int = 0; i < a.length; i++) {
    if(a[i] != null) {
        a[remainingCount] = a[i];
        remainingCount++;
    }
}
a.length = remainingCount;

And option 7 is the same, except that the first loop iterates backwards.


So in conclusion, it doesn’t really matter (at least in Flash) whether you iterate forwards or backwards. You just don’t want to call splice() many times.

 
Flag Post

Not sure if I wrote this right (I checked a case or two and it seems right), but could you bench this too? Just combined your 2 loops into 1.

var current:int = 0;
for (var i:int = 0; i < a.length; i++)
{
	if(i != current)// if not same slot
	{
		a[current] = a[i];
	}
	if (!b) //keep condition << this is not throw away condition! (should be !b)
	{
		current++;
	}
	
}
a.length = current;
trace("end", a);

 
Flag Post

Option 8: 0.0480s

 
Flag Post

Nice! A new fastest method for looping.

 
Flag Post

What if we take option 8 and do ++i instead of i++ (in both places its used)?

IIRC, that’s ~5% faster.

(Also, what is b in if (!b)? By my understanding that evaluates to if(true)…)

 
Flag Post

b is the drop condition. i.e. (i % 13 == 0 || i % 11 == 0)

!b is the keep condition.

 
Flag Post

Actually, the drop condition is a[i] == no, where no is a variable with value "no". The array was populated based on that other condition, though.

And I was using ++i.

 
Flag Post
Originally posted by UnknownGuardian:

b is the drop condition. i.e. (i % 13 == 0 || i % 11 == 0)

!b is the keep condition.

Ah ha. Stand-in condition. Foo == Bar.