Cómo convertir la recursividad en iteración con LoadingCache?

Question

Reescribí por completo esta pregunta ya que la original no tenía solución. Para mantenerlo simple, estoy usando números de Fibonacci, un ejemplo de juguete.

El trivial recursive cached computation termina con una stacktrace muy larga, tal como se esperaba. Por eso me gustaría tener una clase abstracta como IterativeLoadingCache, que podría extenderse como here por algo así como

@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; 
} 

, y que iba a tener cuidado sobre todo el almacenamiento en caché y la computación sin utilizar la recursividad.

Estoy realmente buscando un cálculo eficiente de los números de Fibonacci. Necesito algo que permita usar el almacenamiento en caché junto con funciones recursivas, donde la profundidad de recursión puede ser arbitrariamente alta.

Ya tengo una especie de solución, pero es bastante ineficiente y muy fea, así que espero obtener un buen consejo. También me da curiosidad si alguien más lo necesita o quizás ya lo implementó.

Answer 1

EDIT: cambió la aplicación para permitir un solo cálculo cuando el mismo Expression se pasa como un parámetro en varios hilos.

No utilice una LoadingCache, sólo tiene que almacenar en caché el resultado en eval (una vez que se ha modificado para utilizar iteración en lugar de recursividad):

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

Answer 2

Puesto que usted ha reescrito su pregunta, he aquí una nueva respuesta .

Primero, me parece que su implementación de computeNonRecursivelly es aún recursiva, ya que getOrEnqueue lo llama.

No creo que pueda usar un Cache directamente, porque necesita tener 2 pasos en su computación: uno que establece las dependencias para el valor deseado, y uno que hace el cálculo una vez que se cumplen las dependencias. Sin embargo, solo funcionará si nunca tiene dependencias cíclicas (es el mismo requisito que en la recursión).

De esta manera, puede poner en cola las dependencias que todavía no están en la memoria caché (y sus dependencias, etc.) y luego calcularlas en el orden correcto. Algo a lo largo de las líneas de:

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; 
    } 
} 

Ahora se puede implementar un TwoStepCacheLoader que llama a la caché de forma segura:

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

He corrido una prueba de unidad en él, parece funcionar correctamente.