递归方法的Java记忆化

Question

我正在尝试创建阶乘函数的内存版本。当我调用 factMemoized(4) 时，它第一次计算 4 的阶乘并将其存储在 Map 中。当我再次调用 factMemoized(4) 时，它现在给出存储的结果而不是再次重新计算它。这按预期工作。但是，当我调用 factMemoized(3) 时，它会重新计算该值，尽管它已将 fact(3) 作为计算 fact(4) 的一部分进行计算。有什么方法可以确保即使作为递归调用的一部分计算的值也将存储在 map 中，而无需在 fact() 函数中添加内存函数？

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 函数类来实现内存，覆盖而不是委托(delegate)给未内存的 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);
  }

  //...
};