Java: Automatic Memoization

I have a few functions in my code where it makes much sense (seems even mandatory) to use memoization. I don't want to implement that manually for every function separately. Is the

Solution 1:

Spring 3.1 now provides a @Cacheable annotation, which does exactly this.

As the name implies, @Cacheable is used to demarcate methods that are cacheable - that is, methods for whom the result is stored into the cache so on subsequent invocations (with the same arguments), the value in the cache is returned without having to actually execute the method.

Solution 2:

I came across a memoization library called Tek271 which appears to use annotations to memoize functions as you describe.

Solution 3:

I don't think there is a language native implementation of memoization.

But you can implement it easily, as a decorator of your method. You have to maintain a Map: the key of your Map is the parameter, the value the result.

Here is a simple implementation, for a one-arg method:

Map<Integer, Integer> memoizator = new HashMap<Integer, Integer>();

publicInteger memoizedMethod(Integer param) {

    if (!memoizator.containsKey(param)) {
        memoizator.put(param, method(param));
    } 

    return memoizator.get(param);
}

Solution 4:

You could use the Function interface in Google's guava library to easily achieve what you're after:

import java.util.HashMap;
import java.util.Map;

import com.google.common.base.Function;

publicclassMemoizerTest {
  /**
   * Memoizer takes a function as input, and returns a memoized version of the same function.
   * 
   * @param <F>
   *          the input type of the function
   * @param <T>
   *          the output type of the function
   * @paraminputFunction
   *          the input function to be memoized
   * @return the new memoized function
   */publicstatic <F, T> Function<F, T> memoize(final Function<F, T> inputFunction) {
    returnnewFunction<F, T>() {
      // Holds previous resultsMap<F, T> memoization = newHashMap<F, T>();

      @Overridepublic T apply(final F input) {
        // Check for previous resultsif (!memoization.containsKey(input)) {
          // None exists, so compute and store a new one
          memoization.put(input, inputFunction.apply(input));
        }

        // At this point a result is guaranteed in the memoizationreturn memoization.get(input);
      }
    };
  }

  publicstaticvoidmain(final String[] args) {
    // Define a function (i.e. inplement apply)
    final Function<Integer, Integer> add2 = newFunction<Integer, Integer>() {
      @OverridepublicIntegerapply(final Integer input) {
        System.out.println("Adding 2 to: " + input);
        return input + 2;
      }
    };

    // Memoize the function
    final Function<Integer, Integer> memoizedAdd2 = MemoizerTest.memoize(add2);

    // Exercise the memoized functionSystem.out.println(memoizedAdd2.apply(1));
    System.out.println(memoizedAdd2.apply(2));
    System.out.println(memoizedAdd2.apply(3));
    System.out.println(memoizedAdd2.apply(2));
    System.out.println(memoizedAdd2.apply(4));
    System.out.println(memoizedAdd2.apply(1));
  }
}

Should print:

Adding 2 to: 1

3

Adding 2 to: 2

4

Adding 2 to: 3

5

4

Adding 2 to: 4

6

3

You can see that the 2nd time memoizedAdd2 is called (applied) to the arguments 2 and 1, the computation in the apply is not actually ran, it just fetched the stored results.

Solution 5:

Cyclops offers Memoisation for Functions, Suppliers, Callables, Predicates and by extension methods (via Method References) (see javadoc)

E.g.

Given a variable called that counts the number of time our method is actually called, we can see the memoised function actually executes the method just once.

int called = 0;

cached = Memoise.memoiseQuadFunction(this::addAll);

assertThat(cached.apply(1,2,3,4),equalTo(10));
assertThat(cached.apply(1,2,3,4),equalTo(10));
assertThat(called,equalTo(1));

privateintaddAll(int a,int b,int c, int d){
    called++;
    return a+b+c+d;
}