你的分享就是我们的动力 ---﹥

函数式编程思想:Groovy中的函数式功能,第3部分

时间:2014-12-25 18:23来源:www.chengxuyuans.com 点击:
程序语言能够在越低的层面上为您处理各种细节,其能让你引入错误和复杂性的地方就越少。(一个典型的例子是JVM上的垃圾收集和内存管理)正如我在之前的几部分内容中所强调的那样,函数式语言的特征之一——以及有着函数式功能的动态语言的特征之一——就是他们允许你有选择地放弃对语言和运行时的一些例行细节的控制权。例如,在“Groovy中的函数式功能,第1部分”中,我展示了递归是如何免去了开发者对状态的维护的。在这部分内容中,我会为使用Groovy进行的缓存做同样的说明。

缓存是一种常见的需求(也是难以发现的错误的一个来源)。在面向对象的语言中,缓存通常会发生在数据对象层面,开发者必须自己来对此进行管理。许多函数式编程语言借助被称作制表(memoization)的这种机制来在函数层面构建缓存,在本文中,我会研究函数的两种的缓存用例:类内部(introclass)的和外部调用(external call)的;我还会说明实现缓存的两种备选方案:手动设定状态和制表。

方法层面的缓存


如果你已读过这一文章系列中的任何一部分的话,那就已经了解数字分类这个问题了(第一部分内容中有解释)。本文以一个Groovy版本(源于上一部分内容)作为内容的起点,如清单1所示:

清单1. 用Groovy编写的Classifier

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 '-'
//...

在目前的实现中,我必须为所调用的每个分类方法都重新计算因子的总和。这就是类内部(intraclass)缓存的一个例子:在正常的使用过程中,就每个数字来说,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)第一次的运行时间是577毫秒,而与之相比较的缓存版本,其需要600毫秒来执行第一次的运行。对于这两种情况来说,区别不是很明显。然而,未优化版本第二次的运行时间是280毫秒,第一次和第二次之间的差异可归因于环境因素,比如说垃圾收集等。缓存版本的第二次运行展示了一个巨大的速度提升,运行时间仅为50时毫秒。在进行第二次运行时,所有的值已都被缓存;现在我测量的是从哈希表中读取数据的速度有多快。未优化的第一次运行和缓存的第一次运行之间的差异是微不足道的,但在第二轮运行中就体现得很夸张了。这就是外部缓存(external caching)的一个例子:无论是谁调用这些代码都可以使用全部的这些结果,故第二轮运行的速度非常的快。

对总和的缓存带来了巨大的不同,但也加进来了一些需要权衡的方面。ClassifierCachedSum不再是只纯粹包含静态方法的了,内部的缓存代表了状态,所以我必须把所有与缓存进行交互的方法都改成是非静态的,这会引起一个涟漪效应(ripple effect)。我可以迅速搭建起一些单例模式(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

完全缓存版本(在这些测试运行中,这是一个全新的类和实例变量)第一轮运行的时间花费是411毫秒,而一旦缓存备足内容,第二轮运行就是亮瞎你眼睛的38毫秒。尽管这些结果体现得不错,但这种做法的扩充性却不是特别是好。清单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所示,负责缓存代码的开发者必须操心它的正确性和它的执行情况。这就是变动部分(moving part)的一个完美例子:代码中的状态是开发者必须维护及分析其影响的。

制表(Memoization)


函数式编程努力通过在运行时中构建可重用的机制来尽量减少变动部分。制表(memoization)是一种内置于编程语言中的功能,其能够自动缓存重复出现的函数返回值。换句话说,其自动提供我在清单3和清单6中编写的那些代码。许多函数式语言支持制表,Groovy最近也添加了对它的支持(参见参考资料)。

若要制表Groovy中的某个函数,您把它定义成一个代码块,然后执行memoize()方法来返回一个其结果会被缓存的函数。

制表总和

为了对我在清单3中编写的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赋值为 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

部分制表(partially memoized )版本第一次运行花费的时间大致与非优化版本的第二次运行时间相同,在这两种情况下,内存和其他的环境问题都已得到解决,所以有相似的运行时间是可以理解的。然而,部分制表版本的第二次运行,与手动编写的缓存总和版本一样,显示了夸张的速度提升——其只是对最初的代码在字面上做了两行的修改(把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()     创建闭包的一个能自动调整缓存大小和有缓存大小上下限的缓存变体

在命令式版本中,代码(和责任)为开发者自己所有。函数式语言则构建出了通用的装置——有时带有定制旋钮(体现为备选函数)——您可以把它们应用在普通的构造上。函数是一种基本的语言元素,故这一层面上的优化为你带来了免费的先进功能。本文中的制表版本用在小的数字集合上时要优于手动编写的缓存代码。

结束语


这部分内容说明了贯穿这一文章系列的一个共同主题:函数式编程通过最小化变动部分来把事情变得更为容易。我并排比较了同一个数字分类用例的两个不同的缓存解决方案:使用几种类型的做法来测试相同的数字。手动构建缓存很简单,但会往代码中带入状态和复杂性。使用制表一类的函数式语言功能,我可以在函数层面加入缓存,达成比命令式版本更好的结果(几乎没有怎么改动代码)。函数式编程消除了一些变动部分,允许你专注于解决真正的问题。

资源


学习资料    

1. The Productive Programmer(Neal Ford,O'Reilly Media,2008):Neal Ford的最新著作进一步阐述了这一系列中的许多主题。

2. 闭包制表:了解添加到Groovy 1.8中的制表功能的发布说明。

3. 单例模式:单例是一个有名的Gang of Four设计模式,在面向对象的语言中处理全局状态。

4. “Evolutionary architecture and emergent design: Investigating architecture and design”:了解软件中的固有复杂性和偶发复杂性。

5. 浏览technology bookstore来查找一些关于这些和另外一些技术主题的书籍。  

6. developerWorks Java technology zone:可以找到几百篇关于Java编程的各个方面的文章。

获取产品和技术

1. Groovy:Groovy是JVM上的一种动态语言,其提供了许多的函数式功能。

2. 以最适合你的方式来评估IBM的产品:下载产品的试用版,在线试用产品,在云环境中试用产品,或者在SOA Sandbox中花一些时间来学习如何高效地实现面向服务的架构(Service Oriented Architecture)。

讨论

1. 加入developerWorks社区,浏览开发者驱动的博客、论坛、讨论组和wiki,与其他developerWorks用户建立联系。

关于作者


Neal Ford是一家全球性的IT咨询公司ThoughtWorks的软件架构师和Meme Wrangler。他还设计并编写了一些应用、教材、杂志文章、课件和视频/DVD演示,他是一些跨多种技术的书籍的作者或是编辑,其中包括了最近出版的这本The Productive Programmer。他的工作重点是设计和构建大型的企业级应用,他还是全球范围的开发者大会上的一位国际知名的演讲者。你可以看看他的网站。          

  

译者注:标题配图来自http://www.ibm.com/developerworks/网站

转载注明地址:http://www.chengxuyuans.com/software_engineering/86220.html