java - JAVA递归类中的记忆化

Question

我有一个类，如下所示:

public abstract class Recursion<X, R> {

    protected Recursion<X, R> recursion = this;

    public R recurse(@SuppressWarnings("unchecked") X... xs) {
        return recursion.recurse(xs);
    }
}

private static class LongFib extends Recursion<Long, Long> {
    @Override
    public Long recurse(Long... x) {
        return x[0] <= 2 ? 1 : super.recurse(x[0] - 1) + super.recurse(x[0] - 2);
    }
}

现在我必须构建一个方法，为该方法添加内存功能。

Recursion<Long, Long> fib = new LongFib();
DPified.dpIfy(fib); // after calling this method the fib Object should have Memoization implemented.
long actual = fib.recurse(92L);

我知道内存是如何工作的，但我不知道如何拦截方法调用。有什么建议吗？

Answer 1

据我所知，根据您当前的设计，无法仅通过将 Recursion 对象传递给另一个方法来完全实现记忆化。更好的方法是让 DPified 返回一个启用了内存功能的新 Recursion 对象。

在DPified中，您只需返回一个新的Recursion，它会覆盖recurse方法来实现记忆化。

因为你说你知道记忆化是如何工作的，所以我就直接提供代码。但是，您需要实现 hash 方法(因为您选择采用 X[]，它不能直接与 map /列表配合良好)。

public static Recursion<X, R> dpIfy(Recursion<X, R> original) {
  return new Recursion<X, R>() {
    private Map<Long, R> memo = new HashMap<>();
    public R recurse(X... xs) {
      long hash = hash(xs);
      if (memo.containsKey(hash)) {
        return memo.get(hash);
      } else {
        memo.put(hash, original.recurse(xs));
        return memo.get(hash);
      }
    }
  };
}