函数式思维: Groovy 中的函数式特性,第 3 部分

内存化和缓存

现代的动态语言整合了许多函数式特性,以帮助开发人员完成平常的任务。本文将使用 Groovy 探索在函数级别应用缓存的好处,并将这种缓存方法与一种命令式方法进行对比。本文将演示两种类型的缓存,即方法内缓存和外部缓存,还将探讨命令式和函数式版本的优缺点。

Neal Ford, 软件架构师, ThoughtWorks Inc.

Neal FordNeal Ford 是一家全球性 IT 咨询公司 ThoughtWorks 的软件架构师和 Meme Wrangler。他的工作还包括设计和开发应用程序、教材、杂志文章、课件和视频/DVD 演示,而且他是各种技术书籍的作者或编辑,包括最近的新书 The Productive Programmer。他主要的工作重心是设计和构建大型企业应用程序。他还是全球开发人员会议上的国际知名演说家。请访问他的 Web 站点



2012 年 3 月 12 日

关于本系列

本系列的目标是重新调整您对函数式思维的认识,帮助您以全新的方式看待常见问题,并提升您的日常编码能力。本系列文章将探讨函数编程概念、允许在 Java™ 语言中进行函数编程的框架、在 JVM 上运行的函数编程语言,以及语言设计的未来方向。本系列面向那些了解 Java 及其抽象工作原理,但对函数语言不甚了解的开发人员。

编程语言可为您处理的细节越低级,留给您引入错误和复杂性的地方就越少。(一个经典的例子就是 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)(以备用函数的形式),您可以将它应用到标准结构中。函数是一种基本的语言元素,所以在这一级别的优化会免费为您带来高级的功能。本文中提供了较小数字集的内存化版本的性能高于手写的缓存代码。


结束语

本期文章演示了整个这一系列中一个共同的主题:函数编程最小化的移动部分,简化了程序的编写。我对比介绍了一种常见的数字分类用例的两种不同的缓存解决方案:针对多个类别测试相同的数字。手动建立缓存非常简单,但它为代码添加了状态和复杂性。使用内存化等函数语言特性,我可以在函数级别添加缓存,实现比命令式版本更好的结果(几乎无需更改我的代码)。函数编程消除了移动部分,允许您将精力集中在真正需要解决的问题上。

参考资料

学习

获得产品和技术

  • Groovy:Groovy 是 JVM 上的一种动态语言,提供了许多函数特性。
  • 以最适合您的方式 IBM 产品评估试用版软件:下载产品试用版,在线试用产品,在云环境中使用产品,或在 IBM SOA 人员沙箱 中花几小时学习如何有效实现面向服务的架构。

讨论

  • 加入 developerWorks 中文社区。查看开发人员推动的博客、论坛、群和维基,并与其他 developerWorks 用户交流。

条评论

developerWorks: 登录

标有星(*)号的字段是必填字段。


需要一个 IBM ID?
忘记 IBM ID?


忘记密码?
更改您的密码

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件

 


在您首次登录 developerWorks 时,会为您创建一份个人概要。您的个人概要中的信息(您的姓名、国家/地区,以及公司名称)是公开显示的,而且会随着您发布的任何内容一起显示,除非您选择隐藏您的公司名称。您可以随时更新您的 IBM 帐户。

所有提交的信息确保安全。

选择您的昵称



当您初次登录到 developerWorks 时,将会为您创建一份概要信息,您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。

昵称长度在 3 至 31 个字符之间。 您的昵称在 developerWorks 社区中必须是唯一的,并且出于隐私保护的原因,不能是您的电子邮件地址。

标有星(*)号的字段是必填字段。

(昵称长度在 3 至 31 个字符之间)

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件.

 


所有提交的信息确保安全。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Java technology
ArticleID=801535
ArticleTitle=函数式思维: Groovy 中的函数式特性,第 3 部分
publish-date=03122012