memoize

This is a function "memoizer". The function returns a new function that behaves (mostly) identically to the func argument. However, it saves argument(s) in a special hash along with the return value. If the same argument(s) are given again, it simply returns the previously calculated value, which can save loads of calculation time in some cases. The other significant benefit is that it preserves type, meaning that the compiler will still catch type errors for the memoized function just as if it were the original function.

There are some significant caveats. The arguments should be value arguments (strings, floats, bools, etc.), or have a toString() method that indicates its true value. This is because all arguments (even for Objects) must be represented as strings in the argument hash.

public static function memoize(func:Dynamic , hash_size:Int = 100) : Dynamic {

    var arg_hash = new Hash<Dynamic>();
    var f =  function(args:Array<Dynamic>){
        var arg_string = args.join('|');
        if (arg_hash.exists(arg_string)) return arg_hash.get(arg_string);
        else{
            var ret = Reflect.callMethod({},func,args);
            if(Lambda.count(arg_hash) < hash_size) arg_hash.set(arg_string, ret);
            return ret;
        }
    }
    f = Reflect.makeVarArgs(f);
    return f;
}

Also note: You can replace class functions by declaring them "dynamic"

//Foo.hx
class Foo{
   public static dynamic function bar(x:String){} // some long calculation...
}

as well as in closure definitions:

...
var bar = function(x:String){}
...

Then in your Main routine, you can override the closure or function with a memoized version:

...
bar = memoize(bar);
...

Please note that the overhead for using memoize can be pretty significant on many platforms. Typically it will only save you time when you are constantly performing a time consuming calculation over and over with a limited set of arguments.

version #7387, modified 2009-12-19 19:56:47 by jjdonald