Tuesday, March 18, 2008

Memoization in Java

OnJava in 2003, Tim White gave us generic way to build a memoize in java.
IMHO, Mr. White is trying to use big guns (dynamic proxy, reflection) on a small problem: function composition.

If we use/declare an interface:
public interface IFunc1 {
____R apply(A1 arg1);

then we can do implement Memoize1 (on 1 argument) as: (I use the Scala notation for generics [,] since blogger cuts out the xml devil quotes \<,\>)

public class Memoize1[A1, R] implements IFunc1[A1, R] {
____private final IFunc1[A1, R] func;
____private final Map[A1, R] cache;

____public Memoize1(IFunc1[A1, R] func) {
________this(func,new HashMap[A1, R]());

____public Memoize1(IFunc1 func, Map[A1,R] cache) {
________this.func = func;
________this.cache = cache;

public R apply(A1 arg1) {
____R result = cache.get(arg1);
____if (result == null) {
________result = func.apply(arg1);
____cache.put(arg1, result);
____return result;

That's it. Generic. Composable. Reusable. No schnick-schnack.
Similar memoizer could be provide for IFunc2, IFunc3...
Notice that the Memoize has the same signature as the function it encapsulates.

ps. here is the F# version.


anst said...

I think Tom White's version has two advantages over what you're proposing.
1) From the "academic" point of view, it would be nice if a recursive function memoized its results all the way through to the trivial case upon a call (like you call fib(10) with a naive recursive fib() impl and have fib(9)..fib(1) all memoized). His approach does it, yours doesn't.
2) From the "enterprisey" point of view, the proxy solution allows to leave the legacy code almost untouched. What accepted an object of type 'SophisticatedObjectFactoryManager' (whatever that is and does) will remain untouched or say automatically refactored to accept 'ISophisticatedObjectFactoryManager', an interface; and the same with what is returned. Nobody will bother with introducing IFunc1 into any big real-world system and making their code a pile of 'f.apply(a)'.
P.S.: wrote it and noticed the post was from almost a year ago.

Andrei Pamula said...

Hi anst,

thank your for your comment. I'm glad that somebody reads those entries.

Regarding (1), I'll have to disagree with you: the dynamic proxy acts as a wrapper implementation, and neither my proposal nor Tom White's can optimize a naive recursive fib()
public class Fib implements IFib {
____public int apply(int n) {
________assert n > 0;
________if (n == 0) return 0;
________if (n == 1) return 1;
________return apply(n-1) + apply(n-2);
The proxy can intercept only external calls, it has no access to the internal calls. (in ruby that could be easily solved, in java it is more difficult to instrument that)

Regarding (2) you & Tom White are perfectly right, nobody we'll refactor legacy code to funcs. Given an IoC container, that memoizer could be a very good solution, (caching strategies included)

I probably failed to stress the fact that I wish for more solutions to be more generic, to extract from these ObjectFactoryManagerHandler boiler-plate code higher-level abstractions.

With an advanced (Hindley–Milner) type inference (eg. F#/scala) and closures (or even better lambda expressions) algorithms could be expressed in a much more elegant manner, making a lot of boiler-plate-adapters obsolete.

I wish for these funcs
(c# has them since 2.0)

anst said...

Hello, Andrei.
Indeed, I was wrong about (1). And as for closures, I totally agree.

krishna said...


Probably it is too late to comment.But your solution has same issue similar to the decorator pattern as mentioned in the original post by Tom i.e you need to write Seperate memoizer for each of the new functions IFunc2, IFunc3 etc.I think that's why in Original post Tom went with Dynamic proxies.