Java Memoization of Recursive方法

Question

我正在尝试创建Factorial函数的memoized版本.当我调用factMemoized(4)时,它首次计算4的阶乘并将其存储在Map中.当我再次调用factMemoized(4)时,它现在提供存储的结果,而不是再次重新计算它.这按预期工作.但是,当我调用factMemoized(3)时,它会重新计算该值,尽管它已将事实(3)计算为计算事实(4)的一部分.是否有任何方法可以确保即使作为递归调用的一部分计算的值将存储在地图中而不在fact()函数中添加memoization函数？

import java.util.HashMap;
import java.util.Map;


public class MemoizeBetter {

public static <F, T> Function<F, T> memoize(final Function<F, T> inputFunction) {
    return new Function<F, T>() {
      // Holds previous results
      Map<F, T> memoization = new HashMap<F, T>();

      @Override
      public T apply(final F input) {
        // Check for previous results
        if (!memoization.containsKey(input)) {
          // None exists, so compute and store a new one

          memoization.put(input, inputFunction.apply(input));
        }else{
            System.out.println("Cache hit:"+input);
        }

        // At this point a result is guaranteed in the memoization
        return memoization.get(input);
      }
    };
  }

public static void main(String args[]){


final Function<Integer, Integer> fact = new Function<Integer, Integer>() {
      @Override
      public Integer apply(final Integer input) {
        System.out.println("Fact: " + input);
        if(input == 1)
            return 1;
        else return input * apply(input -1);

      }
    };

    final Function<Integer, Integer> factMemoized = MemoizeBetter.memoize(fact);

    System.out.println("Result:"+ factMemoized.apply(1));
    System.out.println("Result:"+factMemoized.apply(2));
    System.out.println("Result:"+factMemoized.apply(3));
    System.out.println("Result:"+factMemoized.apply(2));
    System.out.println("Result:"+factMemoized.apply(4));
    System.out.println("Result:"+factMemoized.apply(1));    }    
}

interface Function<F,T>{
    T apply(F input);
}

Answer 1

问题是您的 Factorial 函数不会递归调用该函数的记忆版本。

为了解决这个问题，有几种选择。

1. 您可以参数化您的 Factorial 函数并为其提供Function应递归调用的引用。在未记忆的情况下，这将是函数本身；在记忆的情况下，这将是记忆包装。

2. 您可以通过扩展Factorial 函数类来实现记忆化，覆盖而不是委托给未记忆化的apply(). 这很难临时完成，但是有一些实用程序可以动态创建子类（例如，这是实现 AOP 的常见方法）。

3. 您可以首先向基本函数提供有关记忆的完整知识。

这是第一个选项的要点：

interface MemoizableFunction<I, O> extends Function<I, O> {

    //in apply, always recurse to the "recursive Function"
    O apply(I input);

    setRecursiveFunction(Function<? super I, ? extends O>);
}

final MemoizableFunction<Integer, Integer> fact = new MemoizableFunction<Integer, Integer>() {

  private Function<Integer, Integer> recursiveFunction = this;

  @Override
  public Integer apply(final Integer input) {
    System.out.println("Fact: " + input);
    if(input == 1)
        return 1;
    else return input * recursiveFunction.apply(input -1);
  }

  //...
};