Java: Data structure for caching computation result?

Question

I have an expensive computation, the result of which I'd like to cache. Is there some way to make a map with two keys? I'm thinking of something like Map<(Thing1, Thing2), Integer>.

Then I could check:

if (! cache.contains(thing1, thing2)) {
  return computeResult();
}
else {
  return cache.getValue(thing1, thing2);
}

pseudocode. But something along those lines.

Answer 1

If you use Google Collections, its MapMaker class has a makeComputingMap method that does exactly what you described. As a free bonus, it's also thread-safe (implements ConcurrentMap).

As for the two-keys thing, you will have to make a class that contains the two keys, and implement a suitable implementation of equals, hashCode, and (if applicable) compareTo that does the key comparison the way you want it.

Answer 2

You need to create a class that holds Thing1 and Thing2, e.g:

class Things {
    public final Thing1 thing1;
    public final Thing2 thing2;
    public Things(Thing1 thing1, Thing2 thing2) {
      this.thing1 = thing1; 
      this.thing2 = thing2;
    }
    @Override
    public boolean equals(Object obj) { ... }
    @Override
    public int hashCode() { ... };
 }

Then to use it:

Things key = new Things(thing1, thing2);
if (!cache.contains(key) {
    Integer result = computeResult();
    cache.put(key, result);
    return result;
} else {
    return cache.getValue(key);
}

Note you have to implement equals and hashcode to make this code work properly. If you need this code to be thread-safe then have a look at ConcurrentHashMap.

Answer 3

Sounds like you want memoisation. The latest trunk head of Functional Java has a memoising product type P1 that models a computation whose result is cached.

You would use it like this:

P1<Thing> myThing = new P1<Thing>() {
  public Thing _1() {
    return expensiveComputation();
  }
}.memo();

Calling _1() the first time will run the expensive computation and store it in the memo. After that, the memo is returned instead.

For your "two keys", you'd want a simple pair type. Functional Java has this too in the form of the class P2<A, B>. To memoise such a value, simply use P1<P2<A, B>>.

You can also use the Promise<A> class instead of the memoisation. This has been in the library for a while, so you'd just need the latest binary. You would use that as follows:

Promise<Thing> myThing =
  parModule(sequentialStrategy).promise(new P1<Thing>() {
    public Thing _1() {
      return expensiveComputation();
    }
  });

To get the result out, simply call myThing.claim(). Promise<A> also provides methods for mapping functions over the result even if the result is not yet ready.

You need to import static fj.control.parallel.ParModule.parModule and fj.control.parallel.Strategy.sequentialStrategy. If you want the computation to run in its own thread, replace sequentialStrategy with one of the other strategies provided by the Strategy class.