Java: automatic memoization

Question

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 there some way (for example like in Python) I can just use an annotation or do something else so I get this automatically on those functions where I want it?

Answer 1

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>();

public Integer memoizedMethod(Integer param) {

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

    return memoizator.get(param);
}

Answer 2

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

Answer 3

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;

public class MemoizerTest {
  /**
   * 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
   * @param inputFunction
   *          the input function to be memoized
   * @return the new memoized function
   */
  public static <F, T> Function<F, T> memoize(final Function<F, T> inputFunction) {
    return new Function<F, T>() {
      // Holds previous results
      Map<F, T> memoization = new HashMap<F, T>();

      @Override
      public T apply(final F input) {
        // Check for previous results
        if (!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 memoization
        return memoization.get(input);
      }
    };
  }

  public static void main(final String[] args) {
    // Define a function (i.e. inplement apply)
    final Function<Integer, Integer> add2 = new Function<Integer, Integer>() {
      @Override
      public Integer apply(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 function
    System.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.