Hack 79 Fast ActionScript Searches

Searching through arrays and text in ActionScript can be slow. Create fast text search code with some string manipulation tricks.

Although Flash Player 7 performs faster than its predecessors, text and array processing can still take considerable time. When creating code that performs searches, it is typical to use a while or for loop. The trouble with repeated operations such as loops is that Flash isn't truly a compiled language; when publishing a SWF, Flash converts human-readable ActionScript into bytecode that the Flash Player can understand. For every loop iteration, at runtime, the Flash Player has to convert each line of bytecode into executable instructions before it is run.

The code may run faster if you avoid repeated operations in a loop, as shown in the following listing. It implements three versions of a simple search through an array.

method1 = function ( ) {

  // Search through array sequentially

  for (var i = 0; i < arr.length; i++) {

    if (arr[i] == nr) {

      return true;

    }

  }

  return false;

};

method2 = function ( ) {

  // Search through array as an object

  var i:String;

  for (i in arr) {

    if (arr[i] == nr) {

      return true;

    }

  }

  return false;

};

method3 = function ( ) {

  // Search through array by first converting its

  // elements to a single string.

  var searchPos:Number = arr.join(" ").indexOf(nr.toString( ));

  if (searchPos != -1) {

    return true;

  }

  return false;

};

// Create array containing the sequence 0 to 999 to search through

var arr:Array = new Array( );

var elem:Number = 1000;

for (var i = 0; i < elem; i++) {

  arr.push(i);

}

// Determine random number to search for

var nr:Number = Math.floor(Math.random( ) * elem);

trace("searching for:" + nr);

// Test method 1

var sT = getTimer( );

method1( );

eT = getTimer( ) - sT;

trace("time method 1 : " + eT);

// Test method 2

var sT = getTimer( );

method2( );

eT = getTimer( ) - sT;

trace("time method 2 : " + eT);

var sT = getTimer( );

method3( );

eT = getTimer( ) - sT;

trace("time method 3 : " + eT);

First, the code defines an array containing the sequence 0 to 999. Then it picks a random number, nr, between 0 and 999 to search for.

var nr:Number = Math.floor(Math.random( ) * elem);

Our test executes three functions, method1( ), method2( ), and method3( ), which search the array for the number.

The first function, method1( ), is a simple for loop search. It looks at each array element in turn and tests whether it is equal to the number for which we are searching. If the number is found, the function returns true. The second function, method2( ), uses a for...in loop. Finally, the third method, method3( ), doesn't use a loop at all; instead, it builds a string consisting of all entries in the array, separated by spaces (so we will have "0 1 2 3 4 5... 997 998 999"). It then searches for the value nr within it as a string.

You can see the speed of each search by running the code a few times. Optimizing code by benchmark testing [Hack #69] helps diagnose a huge variety of problems.

The third search function, method3( ), is the fastest overall and maintains a constant and low search time. Rather than using loops, it converts our data into strings and uses Flash's string manipulation methods on the result. Because it runs the fewest lines of code (it is the only search out of the three that doesn't use a loop), it is somewhat faster than the other searches. (The Array.join( ) operation required to convert the array into a string is relatively fast because it is executed in C++, the compiled language in which native Flash functions are written.) The String and Array class methods on which this hack relies give relatively fast results in Flash Player 6 and 7. Earlier versions of the Flash Player yield poorer results.

The preceding implementations tell you whether the target value is in the array but not where it is within the array. The speed of the search, however, depends on where in the array the sought-after value is found.

The for loop is the faster of the two loop-based search functions, if the match is found early in the array:

searching for:153

time method 1 : 2

time method 2 : 7

time method 3 : 2

If the search match is made near the middle of the array, then the two loop searches come out even:

searching for:418

time method 1 : 5

time method 2 : 5

time method 3 : 2

If the search match is made toward the end of the array, the second search function is faster than the first. This is because the for...in loop searches properties (array elements in this example) in the reverse order they were created in the searched object, with the last elements created being the first ones searched.

searching for:777

time method 1 : 8

time method 2 : 4

time method 3 : 2

But in all three cases, the third search method is the fastest and has the most consistently predictable search time. If you know the contents of the array aren't changing, you can make it even faster by storing the result of the join( ) method and reusing it in future invocations.

The string search approach slows down when the data set is large, but it is still faster than the other methods for searches up to about 10,000 array elements. Realistically, if you are searching data sets of that magnitude, you should perform the search on a remote server and return the results to Flash via, say, Flash Remoting.

Final Thoughts

Looping is a common way to carry out a repetitive set of operations, but Flash loops can be very time consuming. Recognizing the strengths and weaknesses of these three types of search—element search loop, property search loop, nonlooping string search—allows you to create optimized code for any given application.

—Suggested by Edwin Heijmen