如何使用LoadingCache将递归转换为迭代？（涉及IT技术）

Question

由于原问题无法解决，我完全重写了这个问题。为了保持简单，我使用了斐波那契数列作为一个玩具例子。

这个递归缓存计算方法以一个非常长的堆栈跟踪结束，正如预期的那样。这就是为什么我想要一个抽象类，比如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;
}

我需要一种解决方案，可以处理所有缓存和计算，而不使用递归。这与计算斐波那契数列的效率无关，而是需要允许使用具有任意高递归深度的递归函数和缓存功能。

我已经有了一种解决方案，但它非常低效且难看，所以我希望能得到一些好的建议。我也很想知道是否有其他人需要它或已经实现了它。

- maaartinus

---

你有看过Dr. Heinz M. Kabutz的文章关于Fork/Join与Fibonacci和Karatsuba吗？他的一些想法可能适用。 - OldCurmudgeon

@OldCurmudgeon：现在我有了，它很有趣，但并没有真正帮助到我。 - maaartinus

我找到了这个缓存斐波那契数列的例子，看起来很适用。请看底部的“Playing time”部分。它通过将先前计算出的数字保留在缓存中并清除旧值来工作。通过load方法中语句的仔细排序，避免了递归加载。我不确定是否可以将其扩展到超出“玩具”示例的范围。 - Patrick M

@PatrickM 我相当确定，它不会按照我想要的方式工作。仅仅调用 fibonacciCache.getUnchecked(N) 就意味着你会得到一个深度为 N 的递归，这将导致堆栈溢出。除此之外，他们通过迭代 i 来作弊。如果他们只是调用了 getUnchecked(10) 会发生什么？ - maaartinus

Answer 1

既然你已经重新修改了问题，这里是一个新的答案。

首先，我觉得你的 computeNonRecursivelly 实现仍然是递归的，因为它调用了 getOrEnqueue。

我认为你不能直接使用 Cache，因为你需要在计算中有两个步骤：第一个步骤陈述所需值的依赖关系，第二个步骤在满足依赖关系后进行计算。但是，如果出现循环依赖，则无法正常工作（与递归相同的要求）。

这样，你可以将未在缓存中的依赖项（及其依赖项等）排队，然后按正确顺序进行计算。大致如下：

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

我已经对它进行了单元测试，看起来运行正确。

- Frank Pavageau

---

关于“computeNonRecursivelly still recursive”，你是对的，但这只是从我丑陋的解决方案中提取时犯的错误。该调用可以且必须被删除。 - maaartinus

1. 我不确定是否有办法将更多的工作人员投入到一个问题中，也无法看到两个需要共同依赖的值的并发请求是否可以相互合作。也许通过简单重写getDependenciesToCompute可能是可行的，但我不能确定。我知道这是我从未写过的东西。
2. getDependencies 的想法真的很好。我担心它不适用于像 f(n) = f(n-1) + f(f(log(n))) 这样的疯狂情况，但我想我永远不会需要它。
3. 话虽如此，我感谢您提供的好解决方案。我需要一些时间来评估它。

- maaartinus

还有一个问题：在computeDependencies函数中，你调用了cache.get函数，而cache.get函数可能会再次调用computeDependencies函数，如果期间的键过期了的话。但是这个问题似乎可以找到解决方案。 - maaartinus

即使您在缓存上设置了过期策略，我认为它仍然是可以解决的。如果它是“expireAfterAccess”，那么我认为“getIfPresent”调用将计入访问次数，因此它将有助于维护缓存中的值。如果它是“expireAfterWrite”，则在获取值后进行“put”以维护它也可以。但无论如何，它仍然是一个缓存，因此即使（大多数情况下）被清空，它也可以工作，并且通过按顺序而不是递归处理依赖项，即使需要重新计算值，它也应该有助于保持递归级别较低。 - Frank Pavageau

请参阅跳板技术部分。 - Frank Pavageau

Answer 2

编辑： 更改了实现方式，以允许在多个线程中将相同的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();

- Frank Pavageau

---

这应该可以工作，但是我缺少以下功能：“如果另一个对get或getUnchecked的调用正在加载键的值，则等待该线程完成并返回其加载的值。”虽然我可以自己进行一些锁定，但这可能会显著增加开销。 - maaartinus

这个特性在 Cache.get(K, Callable<V>) 中没有被记录，就像在 LoadingCache.get(K) 中一样，但是由于这两种方法最终都会调用 LocalCache.get(K, CacheLoader)，所以应该可以工作。不确定它是一个真正的特性还是一个可能会改变的实现细节。 - Frank Pavageau

Guava的贡献者在这里：是的，Cache.get(K, Callable)确实保证了这一点。我已经提交了一个问题，以确保文档中更清楚地说明这一点。 - Louis Wasserman

@Frank Pavageau：实际上，你的解决方案和使用CacheLoader一样具有递归性。但这不是你的错，我在要求一些不可能的东西：在计算表达式期间询问子表达式的计算就意味着递归。 我需要想办法使用一些占位符...等我想到更多再回来。 - maaartinus