लोडिंग कैश के साथ पुनरावृत्ति में पुनरावृत्ति को कैसे परिवर्तित करें?

Question

मैं पूरी तरह से इस प्रश्न को फिर से लिखता हूं क्योंकि मूल एक असफल था। इसे सरल रखने के लिए मैं फिबोनाची संख्याओं का खिलौना उदाहरण उपयोग कर रहा हूं।

trivial recursive cached computation एक बहुत लंबे स्टैक्स्ट्रेस के साथ समाप्त होता है, जैसा कि अपेक्षित था। यही कारण है कि मैं IterativeLoadingCache, की तरह एक अमूर्त वर्ग जो मैं की तरह

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

कुछ द्वारा here तरह का विस्तार कर सकते हैं और जो प्रत्यावर्तन का उपयोग किए बिना सभी कैशिंग और गणना के बारे में ध्यान रखना होगा करना चाहते हैं है।

मैं वास्तव में फिबोनाची संख्याओं की कुशल गणना की तलाश नहीं कर रहा हूं। मुझे रिकर्सिव फ़ंक्शंस के साथ कैशिंग का उपयोग करने की अनुमति देने की आवश्यकता है, जहां रिकर्सन गहराई मनमाने ढंग से उच्च हो सकती है।

मुझे पहले से ही एक तरह का समाधान मिला है, लेकिन यह काफी अक्षम और बहुत बदसूरत है, इसलिए मुझे कुछ अच्छी सलाह मिलनी है। मैं उत्सुक हूं अगर किसी और को इसकी आवश्यकता है या शायद इसे पहले ही लागू कर दिया गया है।

Answer 1

संपादित करें: ने एक ही गणना के लिए कार्यान्वयन को बदलने के लिए उसी Expression को कई धागे में पैरामीटर के रूप में पारित किया है।

एक LoadingCache का उपयोग न करें, बस eval में परिणाम कैश (एक बार यह यात्रा प्रत्यावर्तन के बजाय का उपयोग करने के संशोधित किया गया है):

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

आप अपने प्रश्न फिर से लिख दिया के बाद से, यहाँ एक नया जवाब ।

सबसे पहले, यह मुझे लगता है कि computeNonRecursivelly के कार्यान्वयन की तरह मुझे अभी भी रिकर्सिव है, क्योंकि getOrEnqueue इसे कॉल करता है।

मुझे नहीं लगता कि आप सीधे Cache का उपयोग कर सकते हैं, क्योंकि आपको अपनी गणना में 2 कदम रखने की आवश्यकता है: जो वांछित मूल्य के लिए निर्भरता बताता है, और एक निर्भरता मिलने के बाद गणना करता है। यह केवल तभी काम करेगा जब आपके पास चक्रीय निर्भरता न हो, हालांकि (रिकर्सन में यह वही आवश्यकता है)।

इस तरह, आप निर्भरता जो कैश (और उनके निर्भरता, आदि) में पहले से ही नहीं कर रहे हैं कतार फिर उन्हें सही क्रम में गणना कर सकता है। की तर्ज पर कुछ:

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

अब आप एक TwoStepCacheLoader कि कैश सुरक्षित रूप से कॉल को लागू कर सकते हैं:

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

मैं इस पर एक इकाई परीक्षण चलाने के बाद, इसे सही ढंग से चलाने के लिए लगता है।