Geek Answers Handbook

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

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

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

I tried creating a custom object like this:

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 does not work, because the seccond time called by the function, the new cacheKey is not the same object as the first, even if it is the same.

So my question is: is there a data type that will check the properties of the object used as a key for the corresponding key?

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

+4
source share
1 answer

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

Cliff Notes Version:

  • Easy to do regular equality comparison
  • To perform indexing , you need to know more than one object is equal to another - you need to know which object is larger than the other.
  • If all of your properties are primitives, you must put them on the same line and use Object to track them (NOT a Dictionary ).
  • If you need to compare some individual properties for referential equality, you will have a write function to determine which set of properties is greater than the other, and then create your own collection class that uses the output comparison function to implement your own indexing based on binary search.
  • If the number of unique sets of arguments is a few hundred or less and you need a link comparison for your Object argument, just use the Array method and some to naively compare with all cached keys, Only you know how expensive your actual method is, so you decide how much The search (which depends on the number of unique arguments provided to the function) is acceptable.

Equality comparison

To address equality comparisons , it’s simple enough to write code to compare objects for their property values, and not for reference equality. The following function provides a strict comparison, so that both objects must contain exactly the same properties (without additional properties for any permitted object) 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 can speed it up by eliminating the second cycle with a compromise that {A:1, B:2} will be considered equal to {A:1, B:2, C:'An extra property'} .

Indexing

The problem with this in your case is that you lose indexing , that Dictionary provides referential equality, or that Object provides string keys. You will need to compare each new set of function arguments with the entire list of previously seen arguments, for example using Array.some . I use the currentArgs field and the method to avoid generating a new close 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 that the comparison will be O (n) time, where n is an increasing number of unique sets of function arguments.

If all the arguments to your function are primitive, see a very similar question In AS3, where do you draw a line between the Dictionary and the ArrayCollection? . The name does not seem very similar, but the solution in the accepted answer (yes, I wrote it) concerns the same technical problem - using several primitive values ​​as one composite key. The main point in your case:

 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 link is “bigger” than the other (as Dictionary does internally), you will have to sneak into some ugly things since Adobe has not yet provided an API to extract the link “value” / “address”. The best I have found so far is an interesting hack: How can I get an "instance memory location"? in ActionScript? . Without performing a bunch of performance tests, I don’t know if using this hack to compare links will kill the benefits gained by the indexnig binary search tree. Naturally, this will depend on the number of keys.

+3
source

More articles:


All Articles