6

元の質問が解決できなかったため、この質問を完全に書き直しました。簡単にするために、おもちゃの例としてフィボナッチ数を使用しています。

単純な再帰的なキャッシュされた計算は、予想どおり、非常に長いスタック トレースで終了します。そのため、 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;
}

再帰を使用せずにすべてのキャッシュと計算を処理します。

フィボナッチ数の効率的な計算を実際に探しているわけではありません。再帰の深さが任意に高くなる可能性がある再帰関数と一緒にキャッシングを使用できるようにするものが必要です。

私はすでに一種の解決策を持っていますが、それは非常に非効率的で非常に醜いので、良いアドバイスが得られることを願っています. また、他の誰かがそれを必要としているか、またはすでに実装しているかどうかも知りたいです。

4

2 に答える 2

4

質問を書き直したので、ここに新しい回答があります。

まず、それを呼び出すので、あなたの実装computeNonRecursivellyはまだ再帰的であるように見えます。getOrEnqueue

計算には2つのステップが必要なため、直接使用できないと思いますCache.1つは必要な値の依存関係を示し、もう1つは依存関係が満たされたときに計算を実行します。ただし、循環依存関係がない場合にのみ機能します（再帰と同じ要件です）。

そうすれば、まだキャッシュにない依存関係 (およびその依存関係など) をキューに入れ、正しい順序でそれらを計算できます。次の行に沿ったもの：

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

単体テストを実行しましたが、正しく実行されているようです。

于 2012-08-24T11:23:08.113 に答える
3

編集：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();
于 2012-06-22T11:10:12.313 に答える