Come convertire la ricorsione in iterazione con LoadingCache?

Question

Ho completamente riscritto questa domanda perché quella originale era irrisolvibile. Per semplificare, sto usando un numero di Fibonacci come esempio di un giocattolo.

Il trivial recursive cached computation termina con uno stacktrace molto lungo, proprio come previsto. Ecco perché mi piacerebbe avere una classe astratta come IterativeLoadingCache, quale ho potuto estendere come here da qualcosa come

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

e che sarebbe preso cura di tutto il caching e di calcolo senza l'utilizzo di ricorsione.

Sono in realtà non cercando un calcolo efficiente dei numeri di Fibonacci. Ho bisogno di qualcosa che permetta di usare la cache insieme a funzioni ricorsive, dove la profondità di ricorsione può diventare arbitrariamente alta.

Ho già una sorta di soluzione, ma è abbastanza inefficiente e molto brutto, quindi spero di ottenere qualche buon consiglio. Sono anche curioso di sapere se qualcun altro ha bisogno o forse lo ha già implementato.

Answer 1

MODIFICA: modificato l'implementazione per consentire un singolo calcolo quando lo stesso Expression viene passato come parametro in diversi thread.

Non utilizzare un LoadingCache, è sufficiente memorizzare nella cache il risultato in eval (una volta che è stato modificato per utilizzare l'iterazione invece di ricorsione):

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

Dal momento che hai riscritto la tua domanda, ecco una nuova risposta .

In primo luogo, sembra a me come l'implementazione di computeNonRecursivelly è ancora ricorsivo, dal momento getOrEnqueue lo chiama.

Non penso che sia possibile utilizzare direttamente uno Cache, perché è necessario disporre di due passaggi nel calcolo: uno che indica le dipendenze per il valore desiderato e uno che esegue il calcolo una volta soddisfatte le dipendenze. Funzionerà solo se non si hanno mai delle dipendenze cicliche, tuttavia (è lo stesso requisito della ricorsione).

In questo modo, è possibile accodare le dipendenze che non sono già nella cache (e le loro dipendenze, ecc.) Quindi calcolarle nell'ordine corretto. Qualcosa sulla falsariga di:

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

Ora è possibile implementare un TwoStepCacheLoader che chiama la cache in modo sicuro:

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

Ho eseguito un test di unità su di esso, sembra funzionare correttamente.