Best way to cache results of method with multiple parameters - Object as key in Dictionary?

Question

At the beginning of a method I want to check if the method is called with these exact parameters before, and if so, return the result that was returned back then.

At first, with one parameter, I used a Dictionary, but now I need to check 3 parameters (a String, an Object and a boolean).

I tried making a custom Object like so:

var cacheKey:Object = { identifier:identifier, type:type, someBoolean:someBoolean };

//if key already exists, return it (not working)
if (resultCache[cacheKey]) return resultCache[cacheKey];

//else: create result ...

//and save it in the cache
resultCache[cacheKey] = result;

But this doesn't work, because the seccond time the function is called, the new cacheKey is not the same object as the first, even though it's properties are the same.

So my question is: is there a datatype that will check the properties of the object used as key for a matching key?

And what else is my best option? Create a cache for the keys as well? :/

Answer 1

Note there are two aspects to the technical solution: equality comparison and indexing.

The Cliff Notes version:

• It's easy to do custom equality comparison
• In order to perform indexing, you need to know more than whether one object is equal to another -- you need to know which is object is "bigger" than the other.
• If all of your properties are primitives you should squash them into a single string and use an Object to keep track of them (NOT a Dictionary).
• If you need to compare some of the individual properties for reference equality you're going to have a write a function to determine which set of properties is bigger than the other, and then make your own collection class that uses the output of the comparison function to implement its own a binary search tree based indexing.
• If the number of unique sets of arguments is in the several hundreds or less AND you do need reference comparison for your Object argument, just use an Array and the some method to do a naive comparison to all cached keys. Only you know how expensive your actual method is, so it's up to you to decide what lookup cost (which depends on the number of unique arguments provided to the function) is acceptable.

Equality comparison

To address equality comparison it is easy enough to write some code to compare objects for the values of their properties, rather than for reference equality. The following function enforces strict set comparison, so that both objects must contain exactly the same properties (no additional properties on either object allowed) with the same values:

public static propsEqual(obj1:Object, obj2:Object):Boolean {
    for(key1:* in obj1) {
        if(obj2[key1] === undefined)
            return false;
        if(obj2[key1] != obj2[key1])
            return false;
    }
    for(key2:* in obj2) 
        if(obj1[key2] === undefined)
            return false;
    return true;
}

You could speed it up by eliminating the second for loop with the tradeoff that {A:1, B:2} will be deemed equal to {A:1, B:2, C:'An extra property'}.

Indexing

The problem with this in your case is that you lose the indexing that a Dictionary provides for reference equality or that an Object provides for string keys. You would have to compare each new set of function arguments to the entire list of previously seen arguments, such as using Array.some. I use the field currentArgs and the method to avoid generating a new closure every time.

private var cachedArgs:Array = [];
private var currentArgs:Object;

function yourMethod(stringArg:String, objArg:Object, boolArg:Boolean):* {
    currentArgs = { stringArg:stringArg, objArg:objArg, boolArg:boolArg };
    var iveSeenThisBefore:Boolean = cachedArgs.some(compareToCurrent);
    if(!iveSeenThisBefore)
        cachedArgs.push(currentArgs);
}

function compareToCurrent(obj:Object):Boolean {
    return someUtil.propsEqual(obj, currentArgs);
}

This means comparison will be O(n) time, where n is the ever increasing number of unique sets of function arguments.

If all the arguments to your function are primitive, see the very similar question In AS3, where do you draw the line between Dictionary and ArrayCollection?. The title doesn't sound very similar but the solution in the accepted answer (yes I wrote it) addresses the exact same techinical issue -- using multiple primitive values as a single compound key. The basic gist in your case would be:

private var cachedArgs:Object = {};

function yourMethod(stringArg:String, objArg:Object, boolArg:Boolean):* {
    var argKey:String = stringArg + objArg.toString() + (boolArg ? 'T' : 'F');
    if(cachedArgs[argKey] === undefined)
        cachedArgs[argKey] = _yourMethod(stringArg, objArg, boolArg);
    return cachedArgs[argKey];
}

private function _yourMethod(stringArg:String, objArg:Object, boolArg:Boolean):* {
    // Do stuff 
    return something;
}

If you really need to determine which reference is "bigger" than another (as the Dictionary does internally) you're going to have to wade into some ugly stuff, since Adobe has not yet provided any API to retrieve the "value" / "address" of a reference. The best thing I've found so far is this interesting hack: How can I get an instance's "memory location" in ActionScript?. Without doing a bunch of performance tests I don't know if using this hack to compare references will kill the advantages gained by binary search tree indexnig. Naturally it would depend on the number of keys.