Flash browser app ActionScript: how to extract a subset of objects from a sorted array *efficiently*?

Question

I have a browser-deployed Flash app (not an AIR app with access to SQLConnection) and it fetches JSON results from a remote server via HTTPService.

I need to extract subsets from the returned resultset, an array of objects, efficiently. Mutltiple calls through the cloud to the back-end won't do. It all has to happen client-side.

Is there any collection class in Flex ActionScript that can sort an array of objects by one of the properties the objects all have in common, like the Array sortOn method, and then also provides a binary search method can extract a subset of objects from the sorted version of the array without visiting every item in the array and comparing?

E.g. if I have an array of objects and each object had a zip property and a name property, I'd like to be able to extract all objects with zip = 10015 from the a copy of the original array where the copy has been sorted on zip.

Thanks

Answer 1

I am not aware of any inbuilt collection that does a binary search. But you can sort the array using the Array::sortOn method and write your own code for binary search. You can start with something like:

private static search(array:Array, prop:String, value:Object, 
        frm:Number, to:Number):Number
{
  if(to - frm <= 1)
  {
    if(array[frm][prop] == value)
      return frm;
    if(array[to][prop] == value)
      return to;
    return -1;
  }
  var mid:int = (to + frm) / 2;
  //use a compare function that returns -1, 0, +1 based on their relative values
  if(array[mid][prop] == value)
    return mid;
  if(array[mid][prop] > value)
    return search(array, prop, value, frm, mid - 1);
  return search(array, prop, value, mid + 1, to);
}
array.sortOn("zip", Array.NUMERIC);
var index:Number = ClassName.search(array, "zip", "10015", 0, array.length - 1);

Now you can search up and down from the returned index value (if it is != -1) and retrieve the whole subset with zip value = 10015.

---

Btw, if the data is too big to be searched at the client side using normal methods, wouldn't it be big enough to be a bandwidth bottleneck too?

Answer 2

You could use array.sortOn() and then iterate once over the sorted array (starting from 0): when you reach the first match, start returning elements as you iterate forwards, until you stop matching. This returns the entire subset of matching elements, and on average you will be visiting only half the original array (after sorting).

(If this is too slow, it might be quicker,depending on your data, to use a binary search to get a match, then iterate down until you stop matching ie find the first match in the ordered set, then start returning elements as you iterate upwards until you run out of matches... BUT the time saving might be marginal compared to the time needed to do the original sortOn())