Java中的Memoization

Question

好的，在C#中，我可以这样写：

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，我会有溢出异常。(我可能也有类型转换错误) BUt希望我已经表达了我的观点:我可以创建一个类，它可以隐藏纯数学函数(即确定性的，无副作用的函数)的记忆需求，并获得极好的性能提升。

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

Answer 1

在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中，字段或方法名不要大写。它不是标准的，并且使代码更难阅读。

Answer 2

在Java8中，您可以使用computeIfAbsent实现memoization：

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

更多详细信息请点击此处http://rdafbn.blogspot.ie/2015/06/memoize-functions-in-java-8.html

最后，您可以使用cyclops库删除创建memoize泛型方法的样板代码(看看http://static.javadoc.io/com.aol.cyclops/cyclops-functions/4.0.2/com/aol/cyclops/functions/Memoise.html)

Answer 3

查看Guava的cache包。这就是它的用途。