記憶化在Java中

好了，所以在C＃中我可以這樣寫：記憶化在Java中

public class Memorizer<K,TRes> 
{ 
    private Dictionary<K,TRes> _mem; 
    private Func<K,TRes> _function 

    public Memorizer (Func<K,TRes> function) 
    { 
     _function = function; 
     _mem= new Dictionary<K,TRes>(); 
    } 

    public TRes Call(K arg) 
    { 
     if (mem.ContainsKey(arg) 
     { 
      return _mem[arg]; 
     } 
     else 
     { 
      TRes ret=_function(arg); 
      _mem[arg] = ret; 
      return ret; 
     } 
    } 
}

這可能是利用了顯而易見的收益：

public class FactorialCalculator() 
{ 
    private Memorizer<ushort, ulong> _memorizedFactorial; 
    public FactorialCalculator() 
    { 
     _memorizedFactorial = new Memorizer<ushort, ulong> (innerFactorial); 
    } 

    private ulong innerFactorial(ushort x) 
    { 
     return (x=0) ? 1 : x*Factorial(x-1) 
    } 

    public ulong factorial(ushort x) 
    { 
     _memorizedFactorial.Call(x); 
    } 

}

我敢肯定，它可以作出更一般的優雅。而且我知道如果x> 20，會出現溢出異常。（我可能已經在那裏強制轉換的錯誤太）但我希望我做了我的觀點：我可以創建一個類，它可以furful爲純數學函數memoisation需求（即確定的，無副作用的功能）並獲得精彩性能提升。

我該如何在Java中完成類似的事情？

來源

2011-11-22 Lyndon White

我相信，這些被稱爲「memoizer」，而不是「存儲器」。 – Oded

另外* *詞典*，不* Dictionairy *在*「新Dictionairy」*線。 – TacticalCoder

另外，根據素因子分解計算factorial效率更高。對於每個素數p <= n，其出現的次數爲n的一個因子！對於自然數i，就像sum（i * floor（n/pow（p，i）））。 –

您不能在java中將函數作爲數據類型傳遞。要解決這個問題，請使用界面。

public interface ReturnFunction<K, V> { 
    public V getValue(K k); 
}

現在您可以將innerFactorial設置爲數據類型。

public ReturnFunction<Short, Long> innerFactorial = new ReturnFunction<Short, Long>(){ 
    public Long getValue(Short x){ 
     return (x=0) ? 1 : x*Factorial(x-1); 
    } 
};

這可以讓你通過innerFactorial作爲一種數據類型：

_memoizedFactorial = new Memorizer<Short, Long> (innerFactorial);

而且打電話給你寫這個函數：

long someLong = _memoizedFactorial.getValue(someShort);

而且，在Java中不利用字段或方法名稱。這不是標準的，會使代碼更難閱讀。

來源

2011-11-22 14:49:03

查看番石榴的功能界面。不需要重新發明輪子。 –

@John B Thanx從來沒有聽說過它，但它很好。 –

出於理論上的目的，並且因爲爲3行代碼引入額外的libnray而不屑一顧。重新發明車輪沒有任何問題。 –

退房番石榴的cache包。這就是它的目的。

來源

2011-11-22 14:42:01

如果編譯器或運行時可以爲我們做，記憶將是一件好事。如果編譯器/運行時可以安全地假設零副作用方法，它將成爲現實，不是嗎？請參閱http://tshrestha.blogspot.com/2013/04/scala-and-price-of-not-being-purely.html –

您不能創建從<short, ulong> Java中的通用映射，因爲泛型類型參數只能綁定到引用類型。你將不得不使它<Short, Long>涉及包裝原語，並可能會引入一些開銷到你的memoization。

除此之外，翻譯到Java是相當直接的。要知道，你只能memoize的是提供一個有用的equals和hashCode實現類型，你需要使用一個大小有界，線程安全的，弱鍵表例如由MapMaker提供。

來源

2011-11-22 14:46:35

酷了C＃的Func類型的Java equiv是什麼？ –

唯一另外的思想改變是'功能'。按照上述語法，Java沒有真正的功能。你需要提供一個接口，給定一個類型返回另一個類型。番石榴有這樣的功能 - http://docs.guava-libraries.googlecode.com/git-history/v10.0.1/javadoc/com/google/common/base/Function.html –

@JohnB，好點。 –

在Java 8，你可以使用computeIfAbsent實現記憶化：

import java.util.Map; 
import java.util.concurrent.ConcurrentHashMap; 
import java.util.function.Function; 

public class FactorialCalculator { 

public static void main(String[] args) { 

    Function<Integer, Long> factorialFunction = x -> { 
     System.out.println("Calculating factorial for " + x); 
     long fact = 1; 
     for (int i = 1; i <= x; i++) { 
      fact *= i; 
     } 
     return fact; 
    }; 

    Function<Integer, Long> memoziedFactorialFunction = memoise(factorialFunction); 

    System.out.println(memoziedFactorialFunction.apply(5)); 
    System.out.println(memoziedFactorialFunction.apply(5)); 
    System.out.println(memoziedFactorialFunction.apply(5)); 
    System.out.println(memoziedFactorialFunction.apply(5)); 
    System.out.println(memoziedFactorialFunction.apply(6)); 
    System.out.println(memoziedFactorialFunction.apply(6)); 

} 

public static <X, Y> Function<X, Y> memoise(Function<X, Y> fn) { 
    Map<X, Y> pp = new ConcurrentHashMap<X, Y>(); 
    return (a) -> pp.computeIfAbsent(a, fn); 
}

}

結果是：

Calculating factorial for 5 
120 
120 
120 
120 
Calculating factorial for 6 
720 
720

最後，您可以使用cyclops庫刪除創建memoize的通用方法的樣板代碼（看看http://static.javadoc.io/com.aol.cyclops/cyclops-functions/4.0.2/com/aol/cyclops/functions/Memoise.html）

來源

2015-06-11 15:33:51 marcocast

記憶化在Java中

回答

相關問題