遞歸方法的Java記憶

我正在嘗試創建階乘函數的memoized版本。當我調用factMemoized（4）時，它首次計算4的階乘因子並將其存儲在Map中。當我再次調用factMemoized（4）時，它現在給出了存儲的結果，而不是再次重新計算它。這按預期工作。但是，當我將factMemoized（3）稱爲factMemoized（3）時，它會重新計算這個值，儘管它已經將事實（3）計算爲計算事實（4）的一部分。有沒有什麼方法可以確保即使作爲遞歸調用的一部分計算出的值將被存儲在地圖中，而無需在fact（）函數中添加memoization函數？遞歸方法的Java記憶

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

來源

2014-03-25 Tim

記憶地圖正在被覆蓋，即（0,4），它會覆蓋到相同的索引（0,3），確保你的邏輯是正確。 –

的問題是，你的階乘函數不遞歸調用到函數的memoized版本。

要解決這個問題，有幾個選項。

你可以參數化你的階乘的功能，並給它參考Function應該遞歸調用。在未記憶的情況下，這將是功能本身;在備忘錄的情況下，這將是備忘錄的包裝。
您可以通過實施memoization的延伸階乘函數類，覆蓋，而不是委託給時，unmemoized apply()。這很難做到臨時性，但是有些實用程序可以動態創建子類（例如，這是實現AOP的常用方法）。
你可以給基礎函數充分的知識memoization開始。

這是第一個選擇的要點：

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

    //... 
};

來源

2014-03-25 14:52:07

謝謝 - 在所有這些情況下，事實功能需要知道記憶。我正在研究如何對編寫事實功能的人透明。 – Tim

@Tim：在第二種情況下，函數不一定需要知道，但它需要允許子類化。這與Guice對AOP目標的限制類似。事實上，memoization是AOP的一個非常教科書用例。我懷疑有沒有一種簡單的方法來記憶Java中的任何給定的函數，因爲你需要攔截遞歸調用*。 –

謝謝。在clojure中，這非常簡單。（defn f [n] （println「f called with」n）（if（== 1 n）（* n（f（ - n 1））））） def f（memoize f） – Tim

另一種方式來解決這個問題是使用一個數組來存儲已經計算斐波那契數的值。它的工作方式是，如果第n個位置的斐波那契存在於數組的第n個索引處，那麼這個值不會再次計算，而只是從數組中挑選出來。

但是，如果數值不存在於第n個位置的數組中，則計算它的值。下面給出用於這樣的方法斐波納契（）碼 -

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/

來源

2015-04-20 06:11:45 Frank

遞歸方法的Java記憶

回答

相關問題