函数的记忆

记忆于函数而言是指对于需要多次调用的值进行缓存的机制。目前来说，函数式的编程语言普遍都支持这种特性。

如果我们反复调用一个函数，增加一个内部缓存可以提高计算的效率，用更多的内存去换取更高的效率。

但是只有纯函数才可以适用缓存技术，纯函数是没有副作用的函数：它没有引用其他值可变的类字段。除了返回值之外不设置其他的变量，其结果完全由参数决定。

缓存

有两种函数缓存的用法，一种是外部调用，一类是内部缓存。以及两种实现方式，一种是手工管理状态，另外一种是记忆机制。

对于程序，可以用一个HashMap来存放已经计算过的值，提高下次计算的速度。

import java.util.HashMap;
import java.util.Map;

public class CacheValue {

    private static Map<Integer,Boolean> result = new HashMap<>();

    public static boolean isPrime(int num) {

        if (result.containsKey(num)){
            return true;
        }

        for(int i = 2; i <= Math.sqrt(num); i++) {
            if(num % i == 0) {
                result.put(num,false);
                return false;
            }
        }

        result.put(num,true);
        return true;
    }
}

这种方式提高了运算速度，但是函数不再由纯粹的静态方法组成，类有了缓存就有了状态。带来了一系列的问题。缓存有代价：它提高了代码的非本质性和维护成本。

引入记忆

函数式语言通常会引入记忆机制来帮助开发者完成。

Java8中要记忆一个函数，需要先将需要记忆的函数定义成闭包，然后对这个闭包执行获得一个新的函数，以后调用这个新的函数时，结果都会被缓存起来。

由于Java8，暂时在API中没有提供这种记忆机制，这个函数需要自己实现。

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

public class Memoizer<T, U> {

    private final Map<T, U> cache = new ConcurrentHashMap<>();

    private Memoizer() {}
    private Function<T, U> doMemoize(final Function<T, U> function) {
        return input -> cache.computeIfAbsent(input, function::apply);
    }

    public static <T, U> Function<T, U> memoize(final Function<T, U> function) {
        //每个实例都会有独立的cache
        return new Memoizer<T, U>().doMemoize(function);
    }
}

原谅我写的这个count()函数还是不够单纯。。。

public class Memoization {

    Function<Integer,Integer> f = this::count;
    Function<Integer,Integer> g = Memoizer.memoize(f);

    public Integer count(int num){
        int sum =0;
        for (int i = 0; i < num; i++) {
            sum += i;
        }
        return sum;
    }

    public void test(){

        long start = System.currentTimeMillis();
        Integer flag = g.apply(99999999);
        System.out.println(flag);
        System.out.println(System.currentTimeMillis()-start);
        start = System.currentTimeMillis();
        flag = g.apply(99999999);
        System.out.println(flag);
        System.out.println(System.currentTimeMillis()-start);

    }

    public static void main(String args[]){
        Memoization memoization = new Memoization();
        memoization.test();
    }

}

这种记忆一个函数的方式是在操作函数本身，而非函数的结果。而且被记忆的内容该是值不可变的。

所以所有被记忆的函数应该是：

没有副作用的
不依赖任何外部环境。