java - 如何使用 LoadingCache 将递归转换为迭代？

Question

我完全重写了这个问题，因为原来的问题无法解决。为了简单起见，我使用斐波那契数列作为玩具示例。

trivial recursive cached computation正如预期的那样，以非常长的堆栈跟踪结束。这就是为什么我想要一个像 IterativeLoadingCache 这样的抽象类, 我可以扩展为 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;
}

它会在不使用递归的情况下处理所有缓存和计算。

我真的不是在寻找斐波那契数列的有效计算。我需要一些允许将缓存与递归函数一起使用的东西，递归深度可以达到任意高。

我已经找到了一种解决方案，但是它效率很低而且非常丑陋，所以我希望得到一些好的建议。我也很好奇是否有人需要它或者是否已经实现了它。

Answer 1

由于您重写了问题，这里有一个新答案。

首先，在我看来，您对 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);
        }
    }
}

我已经对其进行了单元测试，它似乎运行正常。