Sorting values in ActionScript 3
23rd May, 2009 – 4:05 pmOne of the next big projects at work will involve displaying a list of data to the user, this list will be generated server side and sent down as un-ordered XML, it is up to the client to sort the data and display it to the user. The system will need to be able to sort a large amount of data (at present, the server could be sending down up to 10,000 records) and we needed to find out if this sorting would be fiesable – to find out, I set up a quick little test script which provides a couple of interesting findings:
{
import flash.display.Sprite;
import flash.utils.Dictionary;
import flash.utils.getTimer;
/**
* @author Jonny
*/
public class Sorting extends Sprite
{
public function Sorting()
{
var source1 : Array = this.generateViaIndexOf(10000);
var source2 : Array = this.generateViaDictionary(10000, false);
var source3 : Array = this.generateViaDictionary(10000, true);
this.sort(source1, Array.NUMERIC);
this.sort(source2, Array.NUMERIC);
this.sort(source3, Array.NUMERIC);
debugOutput("indexOf", source1);
debugOutput("nonCast", source2);
debugOutput("cast", source3);
}
private function debugOutput(name : String, values : Array) : void
{
trace(name + "[0] = " + values[0] + ", " + name + "[1] = " + values[1]);
}
private function sort(source : Array, sortMethod : uint) : void
{
var startTime : uint = getTimer();
source.sort(sortMethod);
trace("Array sorted in " + (getTimer() – startTime) + "ms.");
}
private function generateViaDictionary(length : int, castOutput : Boolean) : Array
{
var startTime : int = getTimer();
var pushed : Boolean;
var dictionary : Dictionary = new Dictionary();
while (length–)
{
pushed = false;
while (!pushed)
{
var thisRand : uint = Math.ceil(Math.random() * 100000000);
if (dictionary[thisRand] == undefined)
{
dictionary[thisRand] = true;
pushed = true;
}
}
}
var output : Array = [];
for (var prop : String in dictionary)
{
if (castOutput)
{
output.push(parseInt(prop));
}
else
{
output.push(prop);
}
}
trace("Source Array containing " + output.length + " items created in " + (getTimer() – startTime) + "ms.");
return output;
}
private function generateViaIndexOf(length : int) : Array
{
var startTime : uint = getTimer();
var pushed : Boolean;
var output : Array = [];
while (length–)
{
pushed = false;
while (!pushed)
{
var thisRand : uint = Math.ceil(Math.random() * 100000000);
if (output.indexOf(thisRand) == -1)
{
output.push(thisRand);
pushed = true;
}
}
}
trace("Source Array containing " + output.length + " items created in " + (getTimer() – startTime) + "ms.");
return output;
}
}
}
When run, this code produces the following output:
Source Array containing 10000 items created in 3082ms. Source Array containing 10000 items created in 71ms. Source Array containing 10000 items created in 102ms. Array sorted in 19ms. Array sorted in 312ms. Array sorted in 17ms. indexOf[0] = 4532, indexOf[1] = 14806 nonCast[0] = 3553, nonCast[1] = 6646 cast[0] = 10432, cast[1] = 22513
We can immediatley draw the conclusion that performing Array.indexOf to determine if a value is unique in a given array is woefully inefficient, the use of a Dictionary (serving as a lookup table) is much better. The other interesting point is that Array.sort(Array.NUMERIC) works quicker if the source values are cast to integers (instead of the Strings a for…var…in loop produces).
For those interested, my final stratergy will be to parse the data returned from the Service layer into strongly typed Objects and then store these in a Dictionary mapping User.id => User Object, then when I need to perform a sort I can simply dump the keys from the Dictionary into an Array.