首页 > 代码库 > 10.1.2 使用记忆化缓存结果

10.1.2 使用记忆化缓存结果

10.1.2 使用记忆化缓存结果

 

记忆化(Memoization),可以描述为缓存函数调用的结果,听起来可能有点复杂,但是,技术非常简单。正如我们前面提到的那样,在函数式编程中,大多数函数是没有副作用的,因此,如果我们用相同的参数值,两次调用同一个函数,得到的结果相同。

如果我们要得到与上一次相同的结果,为什么还要麻烦去再一次执行函数呢?相反,我们可以缓存这个结果。如果我们把第一次调用的结果,以字典方式保存起来,第二次调用时,就不必重新计算值了;可以从字典中读取结果,马上返回。清单 10.3 显示了一个函数,计算两个整数的和。

 

计算 10.3 使用了记忆化的加法(F# Interactive)

> open System.Collections.Generic;;

 

> let addSimple(a, b) =     [1]

     printfn"adding %d + %d" a b     <--输出调试信息

     a + b 

;; 

val addSimple : int * int –> int

 

> let add =     [2]

     let cache = newDictionary<_, _>() 

     (fun x –>     <-- 创建使用缓存的函数

       matchcache.TryGetValue(x) with    |

       |true, v –> v                    |从缓存中读取值

       | _-> let v = addSimple(x)         | 或者计算

         cache.Add(x, v)                 |

         v)                            |

;; 

val add : (int * int -> int)

 

> add(2,3);;    |

adding 2 + 3    |

val it : int = 5   | addSimple 只执行一次

              |

> add(2,3);;     |

val it : int = 5   |

 

清单 10.3 的第一部分是通常的加法函数[1],稍许有一点变化,把运行过程记录在控制台上;如果没有这一点,我们就不知道在原始版本和记忆化版本之间,有什么明显的差异,因为从效率的变化上看,在这个示例中实在是太小了。

实现有缓存功能的函数为 add[2];它使用 .NET 中的字典(Dictionary)类型来保存缓存的结果。缓存被声明为局部值,在用 lambda 表达式中使用,指定给 add 值。我们使用的模式,与第八章讨论使用闭包捕获可变状态的相类似。在这里,cache 值也是可变的(因为,字典是可变的哈希表),也由闭包捕获。问题是,对于所有调用 add 函数,我们需要使用相同的 cache 值,所以,必须在函数之前声明,但我们又不希望使它成为全局值。

函数的最后一部分是 lambda 函数本身。当结果没有缓存时,它才使用 addSimple 函数。从F# Interactive 会话中可以看到,进行计算的函数,只在第一次调用时才运行。

这种方法比尾递归的应用更广泛,没有任何副作用1 的函数都适用。因此,在C# 3.0 中也可以成功使用。在下一小节中,我们将使用 C# 3.0,把这段代码写成更通用的版本。

 

-----------

1 这可能有些令人困惑,因为在前面清单中的函数,是有副作用(输出到屏幕)的。这是一种“软副作用”(soft side effect),可以放心地忽略。核心要求是,结果应该只依赖于传递给函数的参数值。

10.1.2 使用记忆化缓存结果