函数式编程中的重要概念（9）记忆化

look_w

记忆化记忆化（memoization）也是函数式编程中的重要概念，其核心思想是以空间换时间，提高函数的执行性能，尤其是使用递归来实现的函数。使用记忆化要求函数具有引用透明性，从而可以把函数的调用结果与调用时的参数关联起来。通常是做法是在函数内部维护一个查找表。查找表的键是输入的参数，对应的值是函数的返回结果。在每次调用时，首先检查内部的查找表，如果存在与输入参数对应的值，则直接返回已经记录的值。否则的话，先进行计算，再用得到的值更新查找表。通过这样的方式可以避免重复的计算。
最典型的展示记忆化应用的例子是计算斐波那契数列 (Fibonacci sequence)。该数列的表达式是        F[n]=F[n-1]+F[n-2](n>=2,F[0]=0,F[1]=1)。清单 15 是斐波那契数列的一个简单实现，直接体现了斐波那契数列的定义。函数 fib        可以正确完成数列的计算，但是性能极差。当输入 n 的值稍微大一些的时候，计算速度就非常之慢，甚至会出现无法完成的情况。这是因为里面有太多的重复计算。比如在计算        fib(4) 的时候，会计算 fib(3) 和 fib(2)。在计算 fib(3) 的时候，也会计算 fib(2)。由于 fib 函数的返回值仅由参数 n 决定，当第一次得出某个 n        对应的结果之后，就可以使用查找表把结果保存下来。这里需要使用 BigInteger 来表示值，因为 fib 函数的值已经超出了 Long 所能表示的范围。
清单 15.        计算斐波那契数列的朴素实现

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

import java.math.BigInteger; public class Fib { public static void main(String[] args) {    System.out.println(fib(40)); } private static BigInteger fib(int n) {    if (n == 0) {      return BigInteger.ZERO;    } else if (n == 1) {      return BigInteger.ONE;    }    return fib(n - 1).add(fib(n - 2)); } }

清单 16 是使用记忆化之后的计算类 FibMemoized。已经计算的值保存在查找表 lookupTable        中。每次计算之前，首先查看查找表中是否有值。改进后的函数的性能有了数量级的提升，即便是 fib(100) 也能很快完成。
清单 16.        使用记忆化的斐波那契数列计算

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

import java.math.BigInteger; import java.util.HashMap; import java.util.Map; public class FibMemoized { public static void main(String[] args) {    System.out.println(fib(100)); } private static Map<Integer, BigInteger> lookupTable = new HashMap<>(); static {    lookupTable.put(0, BigInteger.ZERO);    lookupTable.put(1, BigInteger.ONE); } private static BigInteger fib(int n) {    if (lookupTable.containsKey(n)) {      return lookupTable.get(n);    } else {      BigInteger result = fib(n - 1).add(fib(n - 2));      lookupTable.put(n, result);      return result;    } } }

很多函数式编程库都提供了对记忆化的支持，会在本系列后续的文章中介绍。