Wie konvertiert man Rekursion in Iteration mit LoadingCache?

Question

Ich habe diese Frage komplett neu geschrieben, da das Original unlösbar war. Um es einfach zu halten, verwende ich Fibonacci-Zahlen als Spielzeugbeispiel. Die trivial recursive cached computation endet mit einem sehr langen StackTrace, wie erwartet. Deshalb Ich mag würde eine abstrakte Klasse wie IterativeLoadingCache haben, , die ich wie here durch so etwas wie

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

verlängern könnte und welche würde kümmern sich um all das Caching und Berechnung ohne Rekursion.

Ich bin wirklich nicht auf der Suche nach einer effizienten Berechnung von Fibonacci-Zahlen. Ich brauche etwas, das erlaubt, Caching zusammen mit rekursiven Funktionen zu verwenden, wobei die Rekursionstiefe beliebig hoch werden kann.

Ich habe schon eine Art Lösung, aber es ist ziemlich ineffizient und sehr hässlich, also hoffe ich, einen guten Rat zu bekommen. Ich bin auch neugierig, ob jemand anderes es braucht oder es vielleicht bereits implementiert hat.

Answer 1

EDIT: hat die Implementierung geändert, um eine einzelne Berechnung zu ermöglichen, wenn dieselbe Expression als Parameter in mehreren Threads übergeben wird.

Seien Sie kein LoadingCache, einfach zwischenspeichern das Ergebnis in eval verwenden (wenn es Iteration statt Rekursion zu verwenden, modifiziert wurde):

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

Da Sie Ihre Frage neu geschrieben haben, hier ist eine neue Antwort .

Zuerst sieht es für mich wie Ihre Implementierung von computeNonRecursivelly ist immer noch rekursiv, seit getOrEnqueue nennt es.

Ich glaube nicht, dass Sie eine Cache direkt verwenden können, weil Sie 2 Schritte in Ihrer Berechnung haben müssen: eine, die die Abhängigkeiten für den gewünschten Wert angibt, und eine, die die Berechnung durchführt, sobald die Abhängigkeiten erfüllt sind. Es wird jedoch nur funktionieren, wenn Sie nie zyklische Abhängigkeiten haben (es ist die gleiche Anforderung wie bei der Rekursion).

Auf diese Weise können Sie Abhängigkeiten, die sich nicht bereits im Cache befinden (und deren Abhängigkeiten usw.) in die Warteschlange stellen und sie dann in der richtigen Reihenfolge berechnen. Etwas entlang der Linien von:

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

Jetzt können Sie einen TwoStepCacheLoader implementieren, die den Cache sicher ruft:

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

Ich habe einen Komponententest darauf ausgeführt werden, so scheint es, um korrekt zu funktionieren.