« Emacs mode for AS3
actionscript-mode for EmacsW32 »

Memoization in Actionscript

I love this programming technique, mostly because it is so easy to just drop into your code and instantly trade execution time for memory usage. More information can be found here.

Actionscript
  1. package{
  2.   public class Memo{
  3.  
  4.     static public function Memoize(obj:*,func:Function):Function{
  5.  
  6.       // *** Each argument to func must provide a unique value when
  7.       // *** converted to a string. For example, something that just
  8.       // *** prints out as [Object] will not work.
  9.  
  10.       var hash:Object = {};
  11.  
  12.       var f:Function = function(...args):*{
  13.  
  14.         // Check hash for result.
  15.         var key:String = args.join(",");
  16.            
  17.         var result:* = hash[key];
  18.  
  19.         if(result == null){
  20.  
  21.           result = func.apply(obj, args);
  22.  
  23.           hash[key] = result;
  24.         }
  25.  
  26.         return result;
  27.       }
  28.  
  29.       return f;
  30.     }
  31.   }
  32. }

Example Usage

Actionscript
  1. package{
  2.  
  3.   import Memo;
  4.  
  5.   public class MemoTest{
  6.  
  7.     private var SumSeries_Memo:Function;    // Our memoized variant of the SumSeries function.
  8.  
  9.     public function MemoTest(){
  10.  
  11.       SumSeries_Memo = Memo.Memoize(null,SumSeries);  // Create the memoized version.
  12.  
  13.       var result:Number;
  14.       result = SumSeries_Memo(100,1);   // Computes result, caches it, and returns it.
  15.       result = SumSeries_Memo(100,1);   // Returns cached result.
  16.       result = SumSeries_Memo(100,1);   // Returns cached result.
  17.     }
  18.  
  19.     static public function SumSeries(last:Number,step:Number):Number{
  20.       var result:Number = (((last * last)/step) + last)/2;
  21.       return result;
  22.     }
  23. }

This is the simplest version that I could come up with which works in the greatest variety of cases. If you knew that you were only going to use it with integer arguments, then you could create a faster method to generate keys than converting the arguments to strings and combining them with join.

In case that it isn't clear, memoization only helps if you are calling the memoized function many times with the exact same arguments. Otherwise, it will be slower, due to the overhead of creating the keys and storing the result, and it will be a waste of memory. It is a very nice alternative to creating explicit lookup tables, because you are creating the table on the fly instead of beforehand. If you decide later that you would prefer for the computations to be done beforehand, you can simple call the memoized function sooner and let it cache the results.

If you have a different version of this technique, please post it to the comments area.

This entry was posted on Sunday, January 14th, 2007 at 4:14 pm and is filed under Actionscript.

One Response to “Memoization in Actionscript”

  1. Arthur Debert Says:
    July 19th, 2007 at 4:10 pm

    Thanks for the code. I’ve been implementing an AS memoize today and your post is really helpful. As an extra performance adjustments, I’ve kept a static dictionary, using each initial function as keys so that different instances of the Memo class that wrap the same function can share the same values cache.

    I has this done in AS2, and it was much easier! In as2, functions are real objects and you could create properties on them directly, no need for an external class. I’ve tried to do this in AS3 and I get an error telling me that I cannot create a property on a MethodClosure object, which, unfortunately is supposed to be dynamic but really isn’t.

    Cheers
    Arthur