Java 中的记忆化

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 就会出现溢出异常。 （而且我也可能有类型转换错误） 但希望我表达了我的观点：我可以创建一个类，可以满足纯数学函数（即确定性、无副作用函数）记忆的需求 并获得惊人的性能提升。

我怎样才能在Java中完成类似的事情？

Answer 1

在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

更多详细信息请参见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 2

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 3

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

Answer 4

您无法在 Java 中从 创建泛型映射，因为泛型类型参数仅绑定到引用类型。您必须将其设为，这涉及包装原语，并且可能会给您的记忆带来一些开销。

除此之外，Java 的翻译非常简单。请注意，您只能记住提供有用的 equals 和 hashCode 实现的类型，并且需要使用大小有限制的、线程安全的弱键表例如 MapMaker。