Previous

Flash Data Structures: Array vs. Object · 1105 days ago

This article is meant for flash beginners or flash programmers who may not know about associative arrays.

Early in my flash prgramming days I found that the Array class was very useful for storing data. But I only ever used it numerically:


a = Array();
a[0] = "one";
a[1] = "two";
a[3] = "three";

or


a = Array();
a.push("one");
a.push("two");
a.push("three");

And this works great in for loops:


for (var i; i<a.length; i++) {
  a[i].do_something();
}

But I ran into a problem when storing large amounts of data that needed to be accessed and compared often.

If there were 2 sets of 500 objects in arrays, and changing one object in one set needed to change the corresponding object in another set, you end up with timeouts. Iterating through 500 objects searching for a key just wasn’t cutting it:


// to find object in 'a' array with
// id that equals 'o' object's id
for (var i; i<a.length; i++) {
  if (a[i].id  o.id){
    // ids match
    a[i].do_something();
  }
}

If there were 500 objects checking 500 other objects (250,000 iterations) the flash player would time out every time.


// to find a match between all objects in 'a_one' array
// with all objects in 'a_two' array
for (var i; i<a_one.length; i++) {
  for (var j; j<a_two.length; j++){
    if (a_one[i].id  a_two[j].id){
      // ids match
      a_two[j].do_something();
    }
  }
}

The solution was an associative array.

It kind of gets glossed over in the documentation; so unless you know what to look for (knowledge of other programming languages) you probably wouldn’t find it. The idea is each element in the array is accessed by a unique key instead of a numbered location.


a = Array();
a["key"]      = "one";
a[2]          = "two"; // same as the next line
a["2"]        = "two"; // numbers can be used also
a["id134234"] = "three";
a["id243234"] = "four";

This can be accomplished with a = Array(); but I prefer either using a = new Object(); or creating a new class with its own unique functions, because the length property doesn’t work as expected anyway. So for the example above instead of using the for loop and array.length to locate an object it is found by its unique key:


o[a[id].id].do_something();

But sometimes you need to iterate through an array and execute code on every element. But since the array.length attribute is lost when using asociative arrays:


for (var i in a) {
  trace(a[i]);
}

or to match two arrays as above:


for (var i in a_one) {
  a_two[i].do_something();
}

So in the above example 250,000 if/thens becomes 500. Much faster. The key to these examples is that I set a unique key(id) on each object, and use that as it’s key in the storage object / array (a[o.id] = o;).

The only problem with the for...in loop is that it is lifo (last in first out); or it shows the last item added first whereas an array used with a for loop is fifo (first in first out). One way to change this is:


var b = Array();
for(var i in a){
  b.push(a[i]);
}
for (var i; i<b.length; i++) {
  b[i].do_something();
}

Now this does add time to iterate through the entire object a and create array b; which isn’t very efficient but since flash passes variables as references at least we are not copying the entire a object just making a new array of references.

So eventually I will dig out the custom class I made that allows you to store objects and retrieve by key or numerically. It is not 100% efficient but allows you to use some of the extra features of the Array class such as sorting, and the speed of key lookups of an associative array. You can also use both the for loop or for...in loop. I found this article a few days ago; similar idea but for javascript.

Comment