How to convert recursion to iteration using LoadCache?

Question

I completely rewrote this question since the original was unsolvable. To keep it simple, I use Fibonacci numbers as a toy example.

trivial recursive computational caching ends with a very long stacktrace, as expected. So I would like to have an abstract class like IterativeLoadingCache , which I could distribute as something like here

@Override protected Integer computeNonRecursivelly(Integer key) { final Integer x1 = getOrEnqueue(key-1); final Integer x2 = getOrEnqueue(key-2); if (x1==null) return null; if (x2==null) return null; return x1+x2; } 

and which will take care of all caches and calculations without using recursion.

I'm really not looking for an efficient Fibonacci calculation. I need something to use caching along with recursive functions, where the recursion depth can be arbitrary.

I already have a kind of solution, but it is quite inefficient and very ugly, so I hope to get some good advice. I am also wondering if someone needs it or maybe has already been implemented.

Answer 1

Since you rewrote your question, here is a new answer.

First, it seems to me that your computeNonRecursivelly implementation is still recursive, since getOrEnqueue calls it.

I don’t think you can use Cache directly, because you need to have 2 steps in your calculation: one that defines the dependencies for the required value, and one that performs the calculations after the dependencies are completed. This will only work if you never have circular dependencies (this is the same requirement as with recursion).

Thus, you can queue dependencies that are not already in the cache (and their dependencies, etc.), and then calculate them in the correct order. Sort of:

 public abstract class TwoStepCacheLoader<K, V> extends CacheLoader<K, V> { public abstract Set<K> getDependencies(K key); } public class TwoStepCache<K, V> extends ForwardingLoadingCache<K, V> { private final TwoStepCacheLoader<K, V> loader; private LoadingCache<K, V> cache; public TwoStepCache(TwoStepCacheLoader<K, V> loader) { this.loader = loader; cache = CacheBuilder.newBuilder().build(loader); } @Override public V get(K key) throws ExecutionException { V value = cache.getIfPresent(key); if (value != null) { return value; } Deque<K> toCompute = getDependenciesToCompute(key); return computeDependencies(toCompute); } private Deque<K> getDependenciesToCompute(K key) { Set<K> seen = Sets.newHashSet(key); Deque<K> dependencies = new ArrayDeque<K>(seen), toCompute = new ArrayDeque<K>(seen); do { for (K dependency : loader.getDependencies(dependencies.remove())) { if (seen.add(dependency) && // Deduplication in the dependencies cache.getIfPresent(dependency) == null) { // We need to compute it. toCompute.push(dependency); // We also need its dependencies. dependencies.add(dependency); } } } while (!dependencies.isEmpty()); return toCompute; } private V computeDependencies(Deque<K> toCompute) throws ExecutionException { V value; do { value = cache.get(toCompute.pop()); } while (!toCompute.isEmpty()); // The last computed value is for our key. return value; } @Override public V getUnchecked(K key) { try { return get(key); } catch (ExecutionException e) { throw new UncheckedExecutionException(e.getCause()); } } @Override protected LoadingCache<K, V> delegate() { return cache; } } 

Now you can implement TwoStepCacheLoader , which safely calls the cache:

 public class Fibonacci { private LoadingCache<Integer, Integer> cache = new TwoStepCache<Integer, Integer>(new FibonacciCacheLoader()); public int fibonacci(int n) { return cache.getUnchecked(n); } private class FibonacciCacheLoader extends TwoStepCacheLoader<Integer, Integer> { @Override public Set<Integer> getDependencies(Integer key) { if (key <= 1) { return ImmutableSet.of(); } return ImmutableSet.of(key - 2, key - 1); } @Override public Integer load(Integer key) throws Exception { if (key <= 1) { return 1; } return cache.get(key - 2) + cache.get(key - 1); } } } 

I ran unit test on it, it works correctly.

Answer 2

EDIT: Modified the implementation to allow one calculation when the same Expression is passed as a parameter in multiple threads.

Do not use LoadingCache , just cache the result in eval (once it has been modified to use iteration instead of recursion):

 public Node eval(final Expression e) { if (e==null) return null; return cache.get(e, new Callable<Node>() { @Override public Node call() { final Node n0 = eval(leftExpression(e)); final Node n1 = eval(rightExpression(e)); return new Node(n0, n1); } }); } private final Cache<Expression, Node> cache = CacheBuilder.newBuilder().build();