java - 递归类JAVA中的内存

我有一个看起来像这样的班级：

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

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

最佳答案

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

在DPified中，您只需要返回一个新的Recursion即可，它覆盖了recurse方法以实现备忘录。

因为您说您知道记忆的工作原理，所以我将直接提供代码。但是，您将需要实现hash方法（因为您选择采用的X[]不能直接与“地图/列表”配合使用）。

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