文档章节

程序设计中的计算复用(Computational Reuse)

大数据之路
 大数据之路
发布于 2012/10/04 18:02
字数 2496
阅读 71
收藏 0

从斐波那契数列说起

我想几乎每一个程序员对斐波那契(Fibonacci)数列都不会陌生,在很多教科书或文章中涉及到递归或计算复杂性的地方都会将计算斐波那契数列的程序作为经典示例。如果现在让你以最快的速度用C#写出一个计算斐波那契数列第n个数的函数(不考虑参数小于1或结果溢出等异常情况),我不知你的程序是否会和下列代码类似:

public  static  long  Fib1( long  n)
{
    return  (n == 1 || n == 2) ? 1 : Fib1(n - 1) + Fib1(n - 2);
}

这段代码应该算是短小精悍(执行代码只有一行),直观清晰,而且非常符合许多程序员的代码美学,许多人在面试时写出这样的代码可能心里还会暗爽。但是如果用这段代码试试计算Fib(100)我想就再也爽不起来了,估计下星期甚至下个月前结果很难算得出来。

看来好看的代码未必中用,如果程序在效率不能接受那美观神马的就都是浮云了。如果简单分析一下程序的执行流,就会发现问题在哪,以计算Fibonacci(5)为例:

从上图可以看出,在计算Fib(5)的过程中,Fib(1)计算了两次、Fib(2)计算了3次,Fib(3)计算了两次,本来只需要5次计算就可以完成的任务却计算了9次。这个问题随着规模的增加会愈发凸显,以至于Fib(100)已经无法再可接受的时间内算出。虽然可以通过尾递归优化将双递归变为单递归,但是效果也并不理想。

这是一个非常典型的忽视“计算复用”的例子。计算复用的目标在于保证计算过程中同一计算子过程只进行一次,通过保存子过程计算结果并复用来提高计算效率。其实类似上面的代码出现在很多教科书中,如果是为了展示斐波那契数列的数学特性当然无可厚非,但是作为计算机程序就很有问题了。因为数学和计算科学是有区别的,数学要求严谨和简洁的表达,而计算科学则需要尽量快的得出结果,好的数学公式未必是好的计算公式。这也说明程序设计不是简单的将数学语言翻译为计算机语言就可以了,程序员应该能将数学语言首先翻译成计算科学语言(算法?),然后再翻译成机器语言。因此程序员的工作绝不是机械的,而是要有一定的创造性,所以必要的算法知识对程序员至关重要,因为算法教会程序员如何用最有效率的方式去编写程序。

言归正传,根据以上分析,可以写出一个更高效的斐波那契数列计算程序:

package com.test;

public class fib {
	

	public  static  long  Fib1( long  n)
	{
	     return  (n == 1 || n == 2) ? 1 : Fib1(n - 1) + Fib1(n - 2);
	}
	
	public static long Fib2(long n)
	{
	    if (n == 1 || n == 2)
	    {
	        return 1;
	    }
	    long m1 = 1, m2 = 1;
	    for (long i = 3; i <= n; i++)
	    {
	        m2 = m1 + m2;
	        m1 = m2 - m1;
	    }

	    return m2;
	}
	public static void main(String[] args) {
		
		long startTime=System.nanoTime(); 
		long result = Fib1(30);
		long endTime=System.nanoTime();
		System.out.println("result and time: \nFib1(30): "+
				result+ "\n" +
				"waste of time: "+
				(endTime - startTime)/1.0e9+"s");  
		
		startTime=System.nanoTime(); 
		result = Fib2(101);
		endTime=System.nanoTime();
		System.out.println("result and time: \nFib2(101): "+
				result+ "\n" +
				"waste of time: "+
				(endTime - startTime)/1.0e9+"s");   
	}

}

result and time: 
Fib1(30): 832040
waste of time: 0.009214463s
result and time: 
Fib2(101): 1298777728820984005
waste of time: 5.267E-6s

这段代码可能看起来不如上一段那么优美,但是其效率却是第一段代码不可比拟的。例如计算Fib(40),在我的机器上,第一段代码用时3.5秒,而第二段代码小于0.001秒。这个差距随着规模增大会更明显,例如Fib(100),第一段代码可能需要几天甚至几周,而第二段代码耗时仍然小于0.001秒。天壤之别!

如果从计算复杂性的角度分析,第一段代码的复杂度为O(1.6^n),对数学敏感的朋友应该能体会到这个函数可怕的增长速度,这甚至不是一个多项式级别的复杂度,而第二段代码仅为O(n)。看到如此简单一个例子出现如此差别,还能说程序员学习算法没有用吗。

上面代码对于“计算复用”的思想体现不是很明显,因为我们仅仅需要一个结果,中间结果都被丢弃了,如果是计算1<=i<=n的所有Fib(i),那么计算复用的思想就会体现的比较明显。

矩阵乘法与Strassen算法

下面说一个将计算复用发挥到极致的例子,说实话直到现在每次看到Strassen算法我都觉得震撼,不知Strassen当年是长了何等天才的脑子才发现这么漂亮的一个算法。

矩阵计算在许多领域如机器学习、图形图像处理、模式识别中均占有重要地位。而计算两个n*n矩阵乘积的运算是矩阵计算中常见的计算。由矩阵理论可知,普通方法计算两个n阶方阵的乘积需要进行n^3次乘法计算,其计算复杂度自然是O(n^3)。但是德国数学家Volker Strassen通过拆分矩阵并复用计算结果,发现了一种复杂度为O(n^2.81)的算法,这个算法简单说来如下。

假设n为2的幂(不为2的幂也能计算,这里是为了方便说明),A和B是两个n阶方阵,则A和B分别可以分解成4个n/2阶方阵:

则:

可惜这样经过8次n/2阶方阵相乘,复杂度还是O(n^3),没有降低复杂度。天才的Volker Strassen发现了一种通过计算7次n/2阶方阵来得出n阶方阵乘积的方法。具体来说,假设每个矩阵的积可以写成如下形式:

然后设:

这样通过7次n/2矩阵的相乘计算出P1-P7,然后:

这样就组合出了AB,这个方法的复杂度为O(n^2.81),这个算法实在是太漂亮了。天才!绝对的天才啊!对于这种人除了无限崇敬我真是没有其它想法了,能将计算复用发挥到如此境地,不知世间能有几人。

计算复用对软件开发的启示

也许有的朋友会说,“我又不开发数值计算型程序,也不会接触如此复杂的算法,计算复用与我何干?”。实际上即使开发非数值型程序,计算复用的思想也是大有用途的。例如我曾经在一个真实的PHP开发的行业系统中见过类似这样的代码:

?  

1
2
3
4
5
foreach ( $items  as  $k  => $v ){      
     //...      
     $money  = $v ->money + getTax();      
     //...      
}      

当时我问开发这个程序的人这里getTax的返回值和每个item有关系吗,他说税费是一套复杂的算法算出来的,但是其值固定的。那这里可就太浪费了,每次循环都计算一次,如果改为如下:

?  

1
2
3
4
5
6
$tax  = getTax();      
foreach ( $items  as  $k  => $v ){      
     //...      
     $money  = $v ->money + $tax ;      
     //...      
}      

则可以节省不少计算资源。在后来的沟通中发现这个问题原来是重构的遗留问题,以前系统中的税率计算是写在程序里的,后来发现这个计算越来越多,就使用“Extract Method”重构模式提取成了getTax函数,但是这样的后果就是到处都是getTax调用,有的程序段甚至调用七八次,但是如果应用计算复用的思想,则应该在脚本开始只计算一次税费并保存,后面全都使用这个变量而不是每次调用getTax。

总之,只要某个计算结果与执行上下文无关,并且在一个执行流中超过一次被使用,则应该使用计算复用。

这个例子还算明显的,有时可能不会这么明显,例如我们知道JavaScript中从深层函数中引用全局对象的代价是很高的,因为需要遍历作用域链(当然是隐式的),因此在JS中如果深层函数代码频繁使用全局对象,则要付出很高的代价。如果程序员不懂得对象及作用域链相关知识,则不会发现这种潜在的效率问题,而正确的做法是使用一个局部变量保存对全局对象的引用而不是每次都直接使用全局变量。

很多成熟的产品也处处体现着计算复用的思想,如在PHP中,下面代码可以得到一个数组的元素个数:

echo  count ( $arr );

如果我们来实现,最自然的想法就是遍历数组。但是PHP的开发者明显更聪明,他们在建立数组时同时建立一个与之关联的内部的数量计数变量(对PHP程序员透明),随着数组元素的增减,这个变量也相应增减,每次调用count函数直接返回这个变量即可,这就将count的复杂度从O(n)降为O(1),这也是计算复用的一个典型应用。

另外,其实计算复用和缓存的概念是相通的,很多缓存系统就使用了计算复用的思想。

推荐阅读:

尾调用优化

http://www.ruanyifeng.com/blog/2015/04/tail-call.html

本文转载自:http://www.cnblogs.com/leoo2sk/archive/2011/03/03/computational-reuse.html

共有 人打赏支持
大数据之路
粉丝 1510
博文 516
码字总数 342856
作品 0
武汉
架构师
优先使用对象组合,而不是类继承

极限编程》(Extreme programming)的指导原则之一是“只要能用,就做最简单的”。一个似乎需要继承的设计常常能够戏剧性地使用组合来代替而大简化,从而使其更加灵活。因此,在考虑一个设计时...

jims
2016/11/13
39
0
软件人员推荐书目

软件人员推荐书目(一) 大师篇 一、 科学哲学和管理哲学 【1】 "程序开发心理学"(The Psychology of Computer Programming : Silver Anniversary Edition) 【2】 "系统化思维导论"(An Introd...

LsDimplex
2016/12/06
14
0
UITableView,定制cell

UITableView,定制cell内容1、复习: 设置表视图的行数,章节的个数 -(NSInteger)tableView:(UITableView *)tableView numberOfRowsInSection:(NSInteger)section 绘制cell(UITableViewCell ......

细雨微风轻诉流年
2016/07/07
4
0
小博老师解析设计思想 ——七大设计原则

[引言] 在软件开发的过程中,设计思想通常是最难学习和领悟的,我们经常听到面向对象设计思想、设计模式、面向接口、面向切片 [单一职责原则] 单一职责原则【SINGLE RESPONSIBILITY PRINCIP...

博为峰教研组
2016/12/05
2
0
虚拟技术

操作系统中的所谓“虚拟”是指同过某种技术把一个物理实体变为若干个逻辑上的对应物。用于实现虚拟的技术称为虚拟技术。在操作系统中利用了两种方式实现虚拟技术,即时分复用技术和空分复用技...

hming
2016/08/30
11
0

没有更多内容

加载失败,请刷新页面

加载更多

Coding and Paper Letter(二十四)

资源整理。这一次内容有点多,拆为两篇,这一篇主要针对Coding。 Coding: 1.R语言包geex,用于估计参数的框架和来自R中的一组无偏估计方程(即M-估计)的经验夹层协方差矩阵。 geex 2.R语言...

胖胖雕
15分钟前
0
0
Python中使用SQLite

SQLite: SQLite是一种数据库,Python中集成了SQLite3,所以在Python中使用SQLite,可以直接导入SQLite包,不需要做额外的配置。 更多的SQLite简介和相关知识可以查看专门的教程:http://ww...

akane_oimo
18分钟前
0
0
05《Java核心技术36讲》之几种字符串类有什么区别?

一、提出问题 今天,我们来聊聊日常使用的字符串,别看它似乎很简单,但其实字符串几乎在所有编程语言里都是个特殊的存在,因为不管是数量还是体积,字符串都是大多数应用中的重要组成。 今天...

飞鱼说编程
36分钟前
0
0
Univalsal_ImageLoader源码结构与创建者模式 初步小结

最近在回归看Univalsal_ImageLoader源码,本想自己也实现试试写一个,看源码是为了学习看能否使用,助于自己可以写出有自己逻辑结构的代码。 首先我们初始化ImageLoader的配置初始化的时候,...

DannyCoder
今天
0
0
计算卷积神经网络浮点数运算量

前言 本文主要是介绍了,给定一个卷积神经网络的配置之后,如何大概估算它的浮点数运算量。 相关代码:CalFlops,基于MXNet框架的 Scala 接口实现的一个计算MXNet网络模型运算量的demo。 正文...

Ldpe2G
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部