Optimizing Multidimensional Arrays in ActionScript 3 with Association

You may already know what an associative array is, but even if you don’t it’s almost certain that you’ve used one in the course of your Flash career.

var associativeArray:Object = {}
associativeArray.foo = "foo";
associativeArray.bar = true;
 
trace(associativeArray.foo);

A common dynamic object is in fact an associative array. What this means is that you can use arbitrary keys and map them to values such that they do not have to be in an ordered list, thus associating the key with the value. What you might not have realized however, is that the Array class in ActionScript 3 is itself an associative array. Try this simple experiment:

var a:Array = [];
a[0] = true;
a.push(true);
a.push(true);
a["foo"] = true;
a.push(true);
a.push(true);
a.bar = true;
 
 
trace("for loop\n");
for(var i:int = 0, ilen:int = a.length ; i < ilen ; i++){
	trace(i,a[int(i)]);
}
 
trace("\nfor...in loop\n");
for(var key:String in a){
	trace(key,a[key]);
}

An Array in ActionScript 3 does have additional properties above and beyond the simple array notation. After all, you can push, pop, shift, unshift, map, and filter them. These are all handy tools, but we’re going to look at something a little more basic than even these, for a use-case a little more peculiar… one in which none of those tools will help much.

Let’s take the example of a multidimensional array, a very common form of data storage. Let’s throw a bit of a twist into this requirement however, and say that the x and y dimensions of this array are to be arbitrarily long, but that not all locations in the array might hold any real data. So for example, you might have data stored at a[0][0], and at a[9999999][9999999] and nowhere in between. You have, essentially, a case where you’re searching for needles in a haystack. How would you go about retrieving all the data from the array? You could use a regular set of for loops like this:

 
var multiDimensional:Array = [];
 
// add a value foo to an arbitrary x / y location in the multiDimensional array.
function insertFooAtXY(x:int, y:int, foo:Boolean = true){
	if(multiDimensional[int(x)] === undefined) multiDimensional[int(x)] = [];
	multiDimensional[int(x)][int(y)] = foo;
}
 
this.insertFooAtXY(0,2);
this.insertFooAtXY(10,0);
this.insertFooAtXY(1,69);
this.insertFooAtXY(5,0);
this.insertFooAtXY(900,97);
this.insertFooAtXY(100005,9846);
this.insertFooAtXY(8,5790);
this.insertFooAtXY(9999999,9999999);
this.insertFooAtXY(4587,6547);
this.insertFooAtXY(900,77);
this.insertFooAtXY(16,3);
 
for(var i:int = 0, ilen:int = multiDimensional.length ; i < ilen ; i++){
	if(multiDimensional[int(i)]){
		for(var j:int = 0, jlen:int = multiDimensional[int(i)].length ; j < jlen ; j++){
			if(multiDimensional[int(i)][int(j)] !== undefined){
				trace("x: "+i+" \t\t\ty: "+j+" \t\t\tvalue:"+multiDimensional[int(i)][int(j)]);
			}
		}
	}
}

My average benchmark for this code is about 2100 milliseconds, which is about 2100 reasons why the standard style of array traversal is a really bad idea for this particular use case. This is even *after* the Array best practices of assigning the array length to a variable instead of accessing the length in the loop conditional.

We need a faster way to find those needles in that haystack. Fortunately, we have such a way and it’s called a for…in loop.

for(var key0:String in multiDimensional){
	for(var key1:String in multiDimensional[int(key0)]){
		if(multiDimensional[int(key0)][int(key1)] !== undefined){
			trace("x: "+key0+" \t\t\ty: "+key1+" \t\t\tvalue:"+multiDimensional[int(key0)][int(key1)]);
		}
	}
}

This style of array traversal took 0 milliseconds, which is a nice round number in my book. This works so well because using the for…in loop only accesses the associative properties of the object, and under the hood all the indeces of the AS3 Array are associative. Because there are only a few bits of data to find, you don’t need to go whole-hog and examine every numerical array location, and doing so in this instance is foolhardy. You can even use for…in to easily scale the array to three or four dimensions, something that would cause a horrifying exponential rise in processing time using a for loop.

Right about now you may be wondering about the memory footprint implications of having such a ridiculously large multidimensional array. I have posted this in the source code as well. On my machine, it consumes a mere 0.01MB of memory. I encourage you to test the code by running it in a browser, rather than with your test publish. While the results are favorable with for…in under all circumstances (the time is 0ms regardless), the browser may cause the for loop to take slightly less time, but still leaving you with well over 1000 reasons not to use it.

The obvious tradeoff in using the for…in loop to traverse your array is that the returned indeces are no longer in numerical order. If the only goal is to retrieve an unknown quantity of data from a mostly undefined array, The lack of numerical ordering should not be a showstopper issue in most cases. This isn’t to say that it’s the perfect, or only way to iterate an array. One scenario involving collision detection comes to mind in which the classic for loop is ideal. I may write about that another time.

Tags: , ,