next »

[Craig Stern]

So, I've got this code which goes through an array and removes entries which don't meet a certain standard:

Code:

function cullBadMoves () {
	
	for (i = 0; i < numberComparisonArray.length; i++) {
		
		if (numberComparisonArray[i][0] < minTargetNum) {	//if it doesn't have the minimum target value,
			numberComparisonArray.splice(i, 1);				//delete the entry
		}

etc.

Simple enough, right? The problem is that every time it splices an entry from the array, the elements below it move up, meaning that the next entry gets skipped as 'i' in the for loop increments. Suppose i is 12; numberComparisonArray[12] gets spliced, and the old numberComparisonArray[13] then gets moved up to the 12 position to fill the gap. It isn't ever going to get checked, though, because i then increments to 13, continuing the for loop.

I've tried two methods to fix the skipping problem, and for some reason, both cause Flash to freeze:

1) stick i-- on the line after each numberComparisonArray.splice(i, 1); call
2) count backwards instead, using for (i = numberComparisonArray.length; i >= 0; i--)

Has anyone dealt with this before? Any ideas on how I could resolve this issue in a way that doesn't make Flash commit harakiri?

[John Nesky]

Both of your suggested methods sound good. I don't know why they wouldn't work without more info.

This is how I do it:

Code:

for (var i: int = 0; i < array.length;) {
  if (array[i].removeMe) {
    array.splice(i, 1);
  } else {
    i++;
  }
}

[increpare]

you should start from length-1, not length, when going backwards.

If you're in as3, you can use filter, which constructs a new container given an old one and a predicate on it.  It's tidier than the methods you suggest - not sure about performance though.

[Kunal]

Not sure why your method isn't working. Might it have something to do with the fact that you are using a multidimensional array ?

Probably a stupid suggestion, but is numComparisonArray going to be small enough for you to create another array (with only the valid elements) and then copy that over ?

[raiten]

That's weird, I tried copying and pasting your code and slapping on i--, works fine for me. Doesn't this code work for you?

Code:

numberComparisonArray=[[5],[6],[14],[5],[19],[15],[5],[3],[25]]
minTargetNum=12
for (var i = 0; i < numberComparisonArray.length; i++) {
		if (numberComparisonArray[i][0] < minTargetNum) {	//if it doesn't have the minimum target value,
			numberComparisonArray.splice(i, 1);				//delete the entry
			i--
		}
}

[agj]

Update your Flex SDK (if you're using that)? I had some issues with arrays in older versions.

[st33d]

I do this all the time:

Code:

/* Maintain FX */
private function updateFX():void{
	for(i = 0; i < fx.length; i++){
		if(fx[i].active && onScreen(fx[i].x, fx[i].y, this, fx[i].blit.width)) fx[i].main();
		else {
			fx.splice(i, 1);
			i--;
		}
	}
}

You use i-- after the splice.

If that doesn't work, then "i" is being modified somehow during the for loop. I have many of these self managing lists in my game so I'm pretty confident I've presented a working example.

[Jonathan Whiting]

you should start from length-1, not length, when going backwards.

If you're in as3, you can use filter, which constructs a new container given an old one and a predicate on it.  It's tidier than the methods you suggest - not sure about performance though.

Though I haven't run tests I'd be very surprised if the performance of filter was significantly worse than a more manual method.  It will presumably add numberComparisonArray.length function calls, but that's not a big deal.

I use AS3's filter significantly for say, weeding out 'dead' objects from particle system arrays.  So, I run it every single frame, with larg-ish arrays and without issues.  Sure beats hand-rolling the functionality.

[st33d]

I was wary of filter because of the overhead Flash incurs on method calls.

Code:

package {
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.utils.getTimer;
	
	public class Main extends Sprite {
		
		public function Main():void {
			if (stage) init();
			else addEventListener(Event.ADDED_TO_STAGE, init);
		}
		
		private function init(e:Event = null):void {
			removeEventListener(Event.ADDED_TO_STAGE, init);
			
			
			
			var t:int, i:int, a:Array, j:int;
			var callBack:Function = function(item:int, index:int, array:Array):Boolean{return item == 1; };
			
			t = getTimer();
			for(i = 0; i < 10000; i++) {
				a = [1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1];
				for(j = 0; j < a.length; j++) {
					// run the usual code on each object
				}
				a = a.filter(callBack);
			}
			trace(getTimer() - t);
			
			t = getTimer();
			for(i = 0; i < 10000; i++) {
				a = [1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1];
				for(j = 0; j < a.length; j++) {
					// run the usual code on each object
					if(!(a[j])){
						a.splice(j, 1);
						j--;
					}
				}
			}
			trace(getTimer() - t);
		}
		
	}
	
}

gives:

124
269

Seems filter is actually twice as fast as running splice calls on the fly.

Good to know! 

[increpare]

That's mighty aesthetically convenient!

[Jonathan Whiting]

Seems filter is actually twice as fast as running splice calls on the fly.

Not all that surprising either.  I suspect filter has been carefully implemented, and splice isn't as work free as it appears.  What that code also shows is that both versions are more than fast enough to imply that the operation is not worth worrying about from an optimization perspective unless you're dealing with ludicrously large arrays.

As always, never assume a custom method will be faster than the generic one, and only optimize if/when you *know* something is slow.

All interesting stuff though

[st33d]

I think it's more to do with the array searching routines in Flash being built in to the player, like the BitmapData methods that make copyPixelling fast.

I tried a speed test with array.every() a while ago, and that turned out to be much slower than using a for loop to iterate through all the items.

Testing the above code without any items to prune it turns out that filter ends up being twice as slow as merely iterating through all the array items.

So I would advise in using filter for lots of object creation and destruction and stick to splicing for occasional pruning.

[increpare]

So I would advise in using filter for lots of object creation and destruction and stick to splicing for occasional pruning.

I would advise doing whatever you feel personally is clearest until you notice otherwise (especially given that the OP is about a bug, not optimisation).

[agj]

Seems filter is actually twice as fast as running splice calls on the fly.

Good to know! 

Yeah; I've never even used filter().

[BorisTheBrave]

Filter is not fast. But I've heard, splice is dead slow. For this sort of work, hand implemented linked lists will outperform arrays.

[Craig Stern]

Thanks for the feedback, guys.

[raigan]

Personally, my rule of thumb is "never modify a list while iterating over it"; rather than pruning objects from a list, it's much easier to e.g build a second list by iterating over the input list and skipping the objects you want to "remove", copying the rest.

[bateleur]

Filter is not fast. But I've heard, splice is dead slow. For this sort of work, hand implemented linked lists will outperform arrays.

Further to which: at the point at which your application's performance depends critically on a list it is often correct to use a tree instead. What kind of data structure is best will depend a lot on the kind of access you need to your elements and how often you insert/remove relative to how often you seek.

[Craig Stern]

Probably a stupid suggestion, but is numComparisonArray going to be small enough for you to create another array (with only the valid elements) and then copy that over ?

Not stupid at all--this worked wonderfully. Thanks!

Code:

culledNumberArray = new Array ();
	
	for (var i = 0; i < numberComparisonArray.length; i++) {
		
		if (numberComparisonArray[i][0] >= minTargetNum) {	//if it meets the minimum target value,
			culledNumberArray.push(numberComparisonArray[i]);
		}