函数式思维
Groovy 中的函数式特性，第 3 部分
内存化和缓存
系列内容：
此内容是该系列 # 部分中的第 # 部分： 函数式思维
此内容是该系列的一部分：函数式思维
敬请期待该系列的后续内容。
编程语言可为您处理的细节越低级，留给您引入错误和复杂性的地方就越少。（一个经典的例子就是 JVM 上的垃圾收集和内存管理。正如我在前面几期中着重介绍的，函数编程（以及具有函数式特性的动态语言）的一个特征是，它们允许您选择性地控制语言和运行时的常见细节。举例而言，在 “函数式思维：Groovy 中的函数式特性，第 1 部分” 中，我介绍了回归如何消除让开发人员维护状态的需要。在本期中，我会使用 Groovy 消除对缓存的需要。
缓存是一种常见需求（和难以找到的错误来源）。在面向对象的语言中，缓存通常发生在数据对象级别上，开发人员必须自行管理它。许多函数编程语言通过一种名为内存化（memoization） 的机制在函数 级别上构建缓存。在本文中，我将分析针对函数的两个缓存用例：类内调用与外部调用。我还将演示两种实现缓存的替代方法：手动设计的状态和内存化。
方法级缓存
如果您阅读过本系列的任何一期，您一定熟悉数字分类的问题（在 函数式思维：函数式思考，第 1 部分 中介绍）。本文的出发点是一个 Groovy 版本（来自 函数式思维：Groovy 中的函数式特性，第 2 部分），如清单 1 所示：
清单 1. Groovy 中的分类器
class Classifier {
def static isFactor(number, potential) {
number % potential == 0;
}
def static factorsOf(number) {
(1..number).findAll { i -> isFactor(number, i) }
}
def static sumOfFactors(number) {
factorsOf(number).inject(0, {i, j -> i + j})
}
def static isPerfect(number) {
sumOfFactors(number) == 2 * number
}
def static isAbundant(number) {
sumOfFactors(number) > 2 * number
}
def static isDeficient(number) {
sumOfFactors(number) < 2 * number
}
}清单 1 中的 factorsOf() 方法的内部算法可使用 “函数式思维：运用函数式思维，第 2 部分” 中介绍的技巧进行优化，但对于本示例，我更感兴趣的是函数级缓存。
因为 Classifier 类会分类数字，所以它的常见用途需要通过多种方法运行相同数字来对其进行分类。例如，考虑清单 2 中的代码：
清单 2. 数字分类的常见用途
//... if (Classifier.isPerfect(n)) print '!' else if (Classifier.isAbundant(n)) print '+' else if (Classifier.isDeficient(n)) print '-' //...
在当前的实现中，我必须重新计算我调用的每个分类方法的因数总数。这是一个类内
缓存的示例：在正常使用中，每个数字通常会多次调用 sumOfFactors() 方法。在这种常见用例中，这是一种低效的方法。
缓存总数
一种提高代码效率的方式是利用已完成的繁重工作。因为生成因数的数量比较耗费资源，所以我希望仅对每个数字执行一次计算。最后，我创建一个缓存来存储计算结果，如清单 3 所示：
清单 3. 缓存总数
class ClassifierCachedSum {
private sumCache
ClassifierCachedSum() {
sumCache = [:]
}
def sumOfFactors(number) {
if (sumCache.containsKey(number))
return sumCache[number]
else {
def sum = factorsOf(number).inject(0, {i, j -> i + j})
sumCache.putAt(number, sum)
return sum
}
}
//... remainder of code unchanged
}
在 清单 3 中，我在构造函数中创建了一个名为 sumCache 的哈希函数。在 sumOfFactors() 方法中，我检查参数总数是否已缓存，如果已缓存，则返回它。否则，我执行昂贵的计算，在返回总数之前将它放在缓存中。
代码更加复杂，但结果不言自明。我通过一系列遵循清单 4 中所示模式的单元测试来运行所有示例：
清单 4. 测试
class ClassifierTest {
def final TEST_NUMBER_MAX = 1000
def classifier = new ClassifierCachedSum()
@Test
void classifier_many_checks_without_caching() {
print "Nonoptimized: "
def start = System.currentTimeMillis()
(1..TEST_NUMBER_MAX).each {n ->
if (Classifier.isPerfect(n)) print '!'
else if (Classifier.isAbundant(n)) print '+'
else if (Classifier.isDeficient(n)) print '-'
}
println "\n\t ${System.currentTimeMillis() - start} ms"
print "Nonoptimized (2nd): "
start = System.currentTimeMillis()
(1..TEST_NUMBER_MAX).each {n ->
if (Classifier.isPerfect(n)) print '!'
else if (Classifier.isAbundant(n)) print '+'
else if (Classifier.isDeficient(n)) print '-'
}
println "\n\t ${System.currentTimeMillis() - start} ms"
}当我运行 清单 4 中的测试时，结果表明缓存大有裨益，如清单 5 所示：
清单 5. 分析缓存总数的结果
Test for range 1-1000 Nonoptimized: 577 ms Nonoptimized (2nd): 280 ms Cached sum: 600 ms Cached sum (2nd run): 50 ms
清单 5 表明，没有优化的版本（清单 1 中）首次运行时花了 577ms，而缓存的版本首次运行花了 600ms。这两种情况区别并不大。但是，未优化版本第二次运行花了 280ms。第一次与第二次之间的区别可归因于环境因素，比如垃圾收集。缓存版本的第二次运行速度有了明显的提升，仅花了 50ms。当第二次运行时，所有值都已缓存，现在我测量一下能够多快地从哈希函数中读取数据。未优化的第一次运行和缓存的第一次运行之间的区别可以忽略，但第二次运行的区别非常显著。这是外部缓存 的一个示例：总体结果可供调用代码的实体使用，所以第二次运行非常快。
缓存总和带来了巨大优势，但也带来了牺牲。ClassifierCachedSum 无法再包含纯静态方法。内部缓存表示了状态，所以我必须使所有与缓存交互的方法变成非静态方法，这具有一种涟漪效应。我可以采用某种单一实体解决方案（参见 参考资料），但这也会增加复杂性。因为我控制着缓存变量，所以我必须确保正确性（比如通过测试）。尽管缓存改善了性能，但它不是免费的：它为我的代码添加了额外的复杂性和维护负担（参见 参考资料）。
缓存所有内容
如果缓存总数可以大大加速代码，为什么不缓存所有可能发生的中间结果？这是清单 6 中的目标：
清单 6. 缓存所有内容
class ClassifierCached {
private sumCache, factorCache
ClassifierCached() {
sumCache = [:]
factorCache = [:]
}
def sumOfFactors(number) {
sumCache.containsKey(number) ?
sumCache[number] :
sumCache.putAt(number, factorsOf(number).inject(0, {i, j -> i + j}))
}
def isFactor(number, potential) {
number % potential == 0;
}
def factorsOf(number) {
factorCache.containsKey(number) ?
factorCache[number] :
factorCache.putAt(number, (1..number).findAll { i -> isFactor(number, i) })
}
def isPerfect(number) {
sumOfFactors(number) == 2 * number
}
def isAbundant(number) {
sumOfFactors(number) > 2 * number
}
def isDeficient(number) {
sumOfFactors(number) < 2 * number
}
}
在 清单 6 中的 ClassifierCached 中，我为因数总数和一个数字的因数都添加了缓存。我没有使用如 清单 3 中所示的详细语法，而是使用了三元运算符，它在此示例中的可表达性令人惊奇。例如，在 sumOfFactors() 方法中，我使用三元运算符的条件部分来检查数字的缓存。在 Groovy 中，一个方法的最后一行是方法的返回值，所以如果我找到一个缓存，我会返回缓存的值；否则，我会计算该数字，将它放在缓存中，然后返回该值。（Groovy 的 putAt() 方法返回已添加到哈希函数中的值。）清单 7 给出了结果：
清单 7. 缓存所有内容：测试结果
Test for range 1-1000 Nonoptimized: 577 ms Nonoptimized (2nd): 280 ms Cached sum: 600 ms Cached sum (2nd run): 50 ms Cached: 411 ms Cached (2nd run): 38 ms
完整缓存的版本（这是这些测试运行中的一个全新的类和实例变量）第一次运行花了 411ms，准备好缓存后，第二次运行仅花了 38ms。尽管这些结果还不错，但此方法无法很好地扩展。在清单 8 中，我们给出了测试 5,000 个数字的结果，缓存的版本用于准备的时间要长得多，但仍然在后续运行中拥有非常快的读取时间：
清单 8. 分类 5,000 个数字测试结果
Test for range 1-5000 Nonoptimized: 6199 ms Nonoptimized (2nd): 5064 ms Cached sum: 5962 ms Cached sum (2nd run): 93 ms Cached: 6494 ms Cached (2nd run): 41 ms
10,000 个数字的结果更加惊人，如清单 9 所示：
清单 9. （尝试）分类 10,000 个数字
Test for range 1-10000 Nonoptimized: 43937 ms Nonoptimized (2nd): 39479 ms Cached sum: 44109 ms Cached sum (2nd run): 289 ms Cached: java.lang.OutOfMemoryError: Java heap space
如 清单 9 所示，负责缓存代码的开发人员必须担忧它的正确性和执行条件。这是移动部分 的一个完美的例子：开发人员必须维护和分析受其影响的代码状态。
内存化
函数编程会尽力最小化移动部分，在运行时中构建可重用的机制。内存化 是编程语言中内置的一项特性，它实现对递归函数返回值的自动缓存。换句话说，它自动提供我在 清单 3 和 清单 6 中编写的代码。许多函数语言支持内存化，Groovy 最近也添加了这项支持（参见 参考资料）。
要在 Groovy 中内存化一个函数，则需要将它定义为一个代码块，然后执行 memoize() 方法来返回一个函数，然后缓存这个函数的结果。
内存化总数
为了实现 sumOfFactors() 的缓存，就像我在 清单 3 中所做的一样，我内存化了 sumOfFactors() 方法，如清单 10 中所示：
清单 10. 内存化总数
class ClassifierMemoizedSum {
def static isFactor(number, potential) {
number % potential == 0;
}
def static factorsOf(number) {
(1..number).findAll { i -> isFactor(number, i) }
}
def static sumFactors = { number ->
factorsOf(number).inject(0, {i, j -> i + j})
}
def static sumOfFactors = sumFactors.memoize()
// remainder of code unchanged
}
在 清单 10 中，我将 sumFactors() 方法创建为一个代码块（请注意 = 和参数位置）。这是一个非常通用的方法，也可从某个库获取。为了内存化函数，我分配了名称 sumOfFactors 作为函数引用上的 memoize() 方法调用。
运行内存化的版本会得到清单 11 中所示的结果：
清单 11. 内存化总数：测试结果
Test for range 1-1000 Nonoptimized: 577 ms Nonoptimized (2nd): 280 ms Cached sum: 600 ms Cached sum (2nd run): 50 ms Cached: 411 ms Cached (2nd run): 38 ms Partially Memoized: 228 ms Partially Memoized (2nd): 60 ms
部分内存化的第一次运行所花时间与未优化的第二次运行大体相同。在两种情形下，内存和其他环境问题都已解决，所以，花费类似的时间是合情合理的。但是，部分优化的第二次运行显示出了与手动写入的缓存总数版本同样显著的速度提升，只需对原始代码进行两处更改：将 sumFactors() 更改到一个代码块中，以及让 sumOfFactors() 指向代码块的一个内存化的实例。
内存化所有内容
就像前面缓存所有内容一样，为什么不使用潜在的可重用结果内存化所有内容？分类器的这个版本如清单 12 所示：
清单 12. 内存化所有内容
class ClassifierMemoized {
def static dividesBy = { number, potential ->
number % potential == 0
}
def static isFactor = dividesBy.memoize()
// def static isFactor = dividesBy.memoizeAtMost(100)
def static factorsOf(number) {
(1..number).findAll { i -> isFactor.call(number, i) }
}
def static sumFactors = { number ->
factorsOf(number).inject(0, {i, j -> i + j})
}
def static sumOfFactors = sumFactors.memoize()
def static isPerfect(number) {
sumOfFactors(number) == 2 * number
}
def static isAbundant(number) {
sumOfFactors(number) > 2 * number
}
def static isDeficient(number) {
sumOfFactors(number) < 2 * number
}
}与 清单 6 中所示的缓存所有内容情形一样，内存化所有内容既有优点也有缺点。清单 13 给出了 1,000 个数字的结果：
清单 13. 内存化 1,000 个数字的所有内容
Test for range 1-1000 Nonoptimized: 577 ms Nonoptimized (2nd): 280 ms Cached sum: 600 ms Cached sum (2nd run): 50 ms Cached: 411 ms Cached (2nd run): 38 ms Partially Memoized: 228 ms Partially Memoized (2nd): 60 ms Memoized: 956 ms Memoized(2nd) 19 ms
内存化所有内容会减缓第一次运行的速度，但在所有情形下，后续运行速度都是最快的，但这一点仅适用于较小的数字集。与 清单 8 中测试的命令式缓存解决方案一样，大数字集会显著降低性能。事实上，在 5,000 个数字的情形下，内存化的版本会耗尽内存。但是，命令式方法要强大可靠，则离不开执行上下文的安全保护和小心感知，这是命令式移动部件的另一个示例。通过内存化，可在函数级别上进行优化。请参见清单 14 中的内存化结果：
清单 14. 内存化调节
Test for range 1-10000 Nonoptimized: 41909 ms Nonoptimized (2nd): 22398 ms Memoized: 55685 ms Memoized(2nd) 98 ms
我通过调用 memoizeAtMost(1000) 方法代替 memoize()，生成了如 清单 14 中所示的结果。就像其他支持内存化的语言一样，Groovy 有多种方法来帮助优化结果，如表 1 所示：
表 1. Groovy 中的内存化方法
| 方法 | 描述 |
|---|---|
memoize() | 创建闭包的一个缓存变体 |
memoizeAtMost() | 为闭包创建具有缓存大小上限的缓存变体 |
memoizeAtLeast() | 为闭包创建具有自动缓存大小调节和缓存大小下限的缓存变体 |
memoizeBetween() | 为闭包创建具有自动缓存大小调节和缓存大小上限和下限的缓存变体 |
在命令式变体中，开发人员拥有代码（和相关责任）。函数语言建立了一种通用的机制，有时候，通过使用自定义代码块 (knob)（以备用函数的形式），您可以将它应用到标准结构中。函数是一种基本的语言元素，所以在这一级别的优化会免费为您带来高级的功能。本文中提供了较小数字集的内存化版本的性能高于手写的缓存代码。
结束语
本期文章演示了整个这一系列中一个共同的主题：函数编程最小化的移动部分，简化了程序的编写。我对比介绍了一种常见的数字分类用例的两种不同的缓存解决方案：针对多个类别测试相同的数字。手动建立缓存非常简单，但它为代码添加了状态和复杂性。使用内存化等函数语言特性，我可以在函数级别添加缓存，实现比命令式版本更好的结果（几乎无需更改我的代码）。函数编程消除了移动部分，允许您将精力集中在真正需要解决的问题上。
相关主题
- The Productive Programmer（Neal Ford，O'Reilly Media，2008 年）：Neal Ford 的新书讨论了帮助您提升编程效率的工具和实践。
- 单一实体模式：单一实体是一种著名的 “四人帮” 设计模式，用于处理面向对象语言中的全局状态。
- “演化架构与紧急设计：研究架构和设计”：阅读软件中的基本 与意外 复杂性。
- developerWorks 中国网站 Java 技术专区：这里有数百篇关于 Java 编程各个方面的文章。
- 以最适合您的方式 IBM 产品评估试用版软件：下载产品试用版，在线试用产品，在云环境中使用产品，或在 IBM SOA 人员沙箱 中花几小时学习如何有效实现面向服务的架构。