关于本系列
本系列旨在将您的观点重新定位为实用的心态，帮助您以新的方式看待常见问题并找到改善日常编码的方式。 它探讨了函数式编程的概念，允许使用Java™语言进行函数式编程的框架，在JVM上运行的函数式编程语言以及语言设计的一些未来方向。 该系列面向那些了解Java及其抽象如何工作，但很少或没有使用功能语言经验的开发人员。
编程语言可以为您处理的细节越低，让您引入错误和复杂性的地方就越少。 （经典示例是JVM上的垃圾收集和内存管理。）正如我在前几期中所强调的那样，功能语言和具有功能功能的动态语言的特征之一是，它们使您可以选择性地放弃对平凡的控制。语言和运行时的详细信息。 例如，在“ Groovy的功能特性，第1部分 ”中，我展示了递归如何消除了开发人员维护状态的需要。 在本期中，我对使用Groovy进行缓存也做同样的事情。
缓存是一个常见的要求（也是难以发现的错误的来源）。 在面向对象的语言中，缓存通常发生在数据对象级别，并且开发人员必须自己进行管理。 许多函数式编程语言通过称为备忘录的机制在函数级别构建缓存。 在本文中，我研究了函数的两个缓存用例：类内调用与外部调用。 我还说明了实现缓存的两种替代方法：手工制作的状态和备注。
方法级缓存
如果您已经阅读了本系列的任何一期文章，那么您就会熟悉数字分类的问题（在第一期中有解释）。 本文的起点是Groovy版本（在上一期中派生），如清单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
}
}
可以通过使用我在“从功能上思考，第2部分 ”中介绍的技巧来优化清单1中 factorsOf()方法的内部算法，但是对于此示例，我对函数级缓存更感兴趣。
由于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。 对于这两种情况，差异不明显。 但是，未优化版本的第二次运行得分为280毫秒。 第一和第二之间的差异可以归因于环境因素，例如垃圾收集。 缓存版本的第二次运行显示速度显着提高，得分仅为50ms。 当第二次运行发生时，所有值都将被缓存。 现在，我正在测量从哈希读取数据的速度。 未优化的第一次运行与缓存的第一次运行之间的差异可以忽略不计，但对于第二次运行而言则是巨大的。 这是外部缓存的一个示例：调用代码的人将使用总体结果，因此第二次运行非常快。
缓存总和有很大的不同，但包括一些折衷。 ClassifierCachedSum不再包含纯静态方法。 内部缓存表示状态，因此我必须使与缓存交互的所有方法都是非静态的，这会产生连锁React。 我可以安装一些Singleton解决方案（请参阅参考资料 ），但这也会增加复杂性。 因为我控制缓存变量，所以必须确保正确性（例如，通过使用测试）。 尽管缓存可以提高性能，但它不是免费的：它为我的代码增加了意外的复杂性和维护负担（请参阅参考资料 ）。
缓存一切
如果缓存总和可以大大加快代码的速度，为什么不缓存可能重复出现的每个中间结果呢？ 这是清单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()方法返回一个函数，其结果将被缓存。
记忆总和
为了像清单3一样实现对sumOfFactors()缓存，我sumOfFactors()了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 ，我将名称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() 使用自动缓存大小调整以及缓存大小的上限和下限创建关闭的缓存变体
在命令式版本中，开发人员拥有代码（和责任）。 函数式语言构建了通用的机械（有时带有定制旋钮（以替代功能的形式）），您可以将其应用于标准构造。 函数是基本的语言元素，因此在该级别进行优化可免费提供高级功能。 本文中的记忆版本数量较少，其性能优于手写缓存代码。
结论
这一部分展示了整个系列的一个共同主题：函数式编程通过最大程度地减少运动部件来使事情变得更容易。 对于常见的数字分类用例，我并置了两种不同的缓存解决方案：针对多个类别测试相同的数字。 手工构建缓存很简单，但是却增加了代码的状态性和复杂性。 使用备注等功能语言功能，我可以在功能级别添加缓存，从而获得比命令版本更好的结果（几乎没有更改我的代码）。 功能编程消除了活动部件，使您能够集中精力解决实际问题。
翻译自: https://www.ibm.com/developerworks/java/library/j-ft9/index.html
