16Jun / 2009

Unique records in AS3

I’m sure others already know this little trick – but in case you didn’t…

The filtermethod for Arrays in Actionscript 3.0 comes in handy if you want to (ahem) *filter* certain elements out of your array :


var tmpArray:Array = ["oranges", "apples","oranges", "pineapple", "carrots", "oranges"];
var fruits:Array = tmpArray.filter(function(e, i, a){
   var isUnique:Boolean = (a.indexOf(e) == i);
   return (isUnique);
}, this);
trace(fruits.toString());


Simple really. Basically you define your logic and associate it with the filter method. The filter method then iterates over each item in the Array, executing the logic as it goes (from first to last) and if it returns true, the iterated record will be included in a new Array. If false, it will be excluded.

Posted in Interaction

Tags: , ,

Permalink 2 Comments

  • http://buffered.io/ OJ

    Hey Dan,

    Functions like this are pretty awesome. They’ve got their roots in functional programming, which is where my heart lies!

    Just one thing to look out for: indexOf() is an O(n) function, which means that for each value in the array you’re traversing the whole array. That results in an algorithm of O(n2) complexity. It’ll scale really badly. Bear in mind that everything is fast for small n ;) When you start getting arrays that are really big, you’ll find that performance is woeful.

    Instead you’re looking to get yourself into the position where you can process the array in O(n) time. This means you’re going to have to use something like a map to keep track, rather than constantly reprocessing the list. For example:


    var map:Object = new Object();
    var fruits:Array = tmpArray.filter(function(e, i, a){
     if(map[e] == null){
      map[e] = true;
      return true;
     }
     return false;
    }, this);

    Here you can see that we’re searching for items in an object/map rather than parsing the array. If the item is found, we indicate that it was already parsed. If it wasn’t found, we add it to the map and indicate that it’s unique.

    Another approach is to brute-force convert the array to a set/map then convert it back. But that doesn’t preserve ordering in the array.

    For larger arrays, this will be substantially quicker than your current approach :)

    Cheers mate, keep the posts coming! Great to have you blogging again.
    OJ

  • dan

    Thanks for the heads up OJ :)

    Optimisation for performance is something that I need to explore more of – im constantly looking for ways to optimise the code, but often its about reducing code, not improving performance.

    For indexOf() (for example) – how does one know that it’s O(n) – is this something you really need to have studied or is there some cheat sheet that highlights these tidbits of wisdom?