Мемоизация рекурсивного метода в Java

Я пытаюсь создать мемоизированную версию функции Factorial. Когда я вызываю factMemoized (4), он впервые вычисляет факториал 4 и сохраняет его в Map. Когда я снова вызываю factMemoized (4), теперь он дает сохраненный результат вместо его повторного вычисления. Это работает, как ожидалось. Но когда я вызываю factMemoized (3), он пересчитывает значение, несмотря на то, что он вычислил факт (3) как часть вычисления факта (4). Есть ли способ убедиться, что даже значения, вычисленные как часть рекурсивных вызовов, будут сохранены на карте без добавления функции мемоизации в функцию 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);
}

java memoization
person Tim    schedule 25.03.2014    source источник
comment
карта запоминания перезаписывается, т.е. (0,4), и она будет перезаписана с тем же индексом (0,3), убедитесь, что ваша логика верна.   -  person praveen_mohan    schedule 25.03.2014

Ответы (2)


arrow_upward
3
arrow_downward

Проблема в том, что ваша функция Factorial не вызывает рекурсивно в мемоизированную версию функции.

Чтобы исправить это, есть несколько вариантов.

  1. Вы можете параметризовать свою функцию Factorial и дать ей ссылку на Function, который она должна вызывать рекурсивно. В случае без запоминания это будет сама функция; в мемоизированном случае это будет мемоизирующая обертка.

  2. Вы можете реализовать мемоизацию посредством расширения класса функции Factorial, переопределив, а не делегируя немомизированный apply(). Это сложно сделать специально, но существуют утилиты для динамического создания подклассов (например, это распространенный способ реализации АОП).

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

  //...
};
person Mark Peters    schedule 25.03.2014
comment
Спасибо - во всех этих случаях функция фактов должна знать о запоминании. Я ищу способы сделать это прозрачным для парня, который пишет функцию фактов. - person Tim; 25.03.2014
comment
@Tim: Во втором случае функция не обязательно должна знать, но она должна разрешить создание подклассов. Это похоже на ограничения, которые поставщики АОП, такие как Guice, накладывают на свои цели АОП. Фактически, мемоизация - это очень хрестоматийный пример использования АОП. Я сомневаюсь, что есть простой способ запоминать любую заданную функцию в Java, потому что вам нужно перехватить рекурсивный вызов как-то. - person Mark Peters; 25.03.2014
comment
Спасибо. В Clojure это довольно просто. (defn f [n] (println f вызывается с n) (if (== 1 n) 1 (* n (f (- n 1))))) def f (мемоизирует f) - person Tim; 25.03.2014
comment
@ Тим: Разве это не та же проблема? Например, см. Этот вопрос о запоминании рекурсивных функций в Clojure (в данном случае Фибоначчи): stackoverflow.com/questions/3906831/. Похоже, что ваш подход в Clojure имеет ту же проблему, что и в Java. Принятый ответ, похоже, хакерски исправляет среду функции, чтобы она вызывала мемоизированный fib (по сути, мое первое предложение). Следующий самый высокий ответ просто рекурсивно вызывает мемоизированный fib (мое третье предложение). - person Mark Peters; 25.03.2014

arrow_upward
1
arrow_downward

Другой способ решить эту проблему - использовать массив для хранения уже вычисленных значений Фибоначчи. Это работает так: если фибоначчи для n-й позиции существует в n-м индексе массива, то это значение не вычисляется снова, а просто берется из массива.

Однако, если значение отсутствует в массиве на n-й позиции, оно рассчитывается. Ниже приведен код для такого метода fibonacci () -

public static long fibonacci(long n){
    long fibValue=0;
    if(n==0 ){
        return 0;
    }else if(n==1){
        return 1;
    }else if(fibArray[(int)n]!=0){
        return fibArray[(int)n];    
    }
    else{
        fibValue=fibonacci(n-1)+fibonacci(n-2);
        fibArray[(int) n]=fibValue;
        return fibValue;
    }
}

Обратите внимание, что этот метод использует глобальный (уровень класса) статический массив fibArray []. Чтобы просмотреть весь код с пояснениями, вы также можете увидеть следующее - http://www.javabrahman.com/gen-java-programs/recursive-fibonacci-in-java-with-memoization/

person Frank    schedule 20.04.2015