文档章节

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

大数据之路
 大数据之路
发布于 2012/10/04 18:02
字数 2496
阅读 70
收藏 0
点赞 0
评论 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

© 著作权归作者所有

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

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

jims ⋅ 2016/11/13 ⋅ 0

软件人员推荐书目

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

LsDimplex ⋅ 2016/12/06 ⋅ 0

UITableView,定制cell

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

细雨微风轻诉流年 ⋅ 2016/07/07 ⋅ 0

小博老师解析设计思想 ——七大设计原则

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

博为峰教研组 ⋅ 2016/12/05 ⋅ 0

虚拟技术

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

hming ⋅ 2016/08/30 ⋅ 0

设计模式学习笔记七:常用设计模式原则总结

前面学习了一部分创建型模式,发现了一个比设计模式更重要的东西:设计模式原则。对于设计模式来说,为什么这个模式要这样解决这个问题,而另一个模式要那样,它们背后都遵循的就是永恒的设计...

长平狐 ⋅ 2013/06/17 ⋅ 0

DDL概念

DDL 数据库模式定义语言 DDL (Data Definition Language),是用于描述数据库中要存储的现实世界实体的语言。一个数据库模式包含该数据库中所有实体的描述定义。 这些定义包括结构定义、操作方...

恋空御月 ⋅ 2016/07/14 ⋅ 0

操作系统介绍

操作系统介绍 操作系统就是一个协调、管理和控制计算机硬件资源和软件资源的控制程序 操作系统位于计算机硬件与应用软件之间,本质也是一个软件。操作系统由操作系统的内核(运行于内核态,管...

迟到的栋子 ⋅ 2017/08/31 ⋅ 0

javascript的策略模式(一)

在程序设计中我们往往会遇到实现某一功能有多种方案可以选择。比如一个压缩算法,我们可以选择zip算法,也可以选择gzip算法。这些算法灵活多样,而且可以随意互相替换。 实例:按照不同等级计...

stone_ ⋅ 2016/05/17 ⋅ 0

Tensorflow Error笔记1

愿天堂没有Tensorflow! 阿门。 ValueError: Variable conv1/weights already exists, disallowed. Did you mean to set reuse=True in VarScope? Originally defined at: 将一个模型训练好,......

BookThief ⋅ 2017/07/11 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

内核线程、轻量级进程、用户线程

线程与进程概念 在现代操作系统中,进程支持多线程。 进程是资源管理的最小单元; 线程是程序执行的最小单元。 即线程作为调度和分配的基本单位,进程作为资源分配的基本单位 一个进程的组成...

117 ⋅ 21分钟前 ⋅ 0

elasticsearch2.4.6升级为elasticsearch-5.5.0的经历

将elasticsearch-5.5.0 中的配置 path.data 指向原来的数据路径 即 path.data: /usr/local/src/elasticsearch-2.4.6/data 注意: elasticsearch-5.5.0 需要将jdk版本升级到1.8...

晨猫 ⋅ 21分钟前 ⋅ 1

lvm讲解 磁盘故障小案例

1

oschina130111 ⋅ 25分钟前 ⋅ 0

那些提升开发人员工作效率的在线工具

本文转载自公众号 Hollis 作为一个Java开发人员,经常要和各种各样的工具打交道,除了我们常用的IDE工具以外,其实还有很多工具是我们在日常开发及学习过程中要经常使用到的。 Hollis偏爱使用...

时刻在奔跑 ⋅ 38分钟前 ⋅ 0

restful风格 实现DELETE PUT请求 的web.xml的配置

import org.springframework.beans.factory.annotation.Autowired; import org.springframework.http.HttpStatus; import org.springframework.http.ResponseEntity; import org.springframe......

泉天下 ⋅ 43分钟前 ⋅ 0

Shell数组

Shell数组 Shell在编程方面比Windows批处理强大很多,无论是在循环、运算。 bash支持一维数组(不支持多维数组),并且没有限定数组的大小。类似与C语言,数组元素的下标由0开始编号。获取数...

蜗牛奔跑 ⋅ 52分钟前 ⋅ 0

nmap为了开发方便 可以做简单的修改

因为nmap扫描是默认使用的是nse脚本,但是在开发的过程中需要修改后缀(主要是因为后缀为lua才能显示高亮,所以这里用一个取巧的办法) nse_main.lua文件中我们找到如下代码 local t, path = cn...

超级大黑猫 ⋅ 56分钟前 ⋅ 0

springmvc获取axios数据为null情况

场景:前端用了vue没有用ajax与后台通信,用了axios,但是在代码运行过程中发现axios传递到后台的值接受到数据为null。 问题原因:此处的问题在与axios返回给后台的数据为json类型的,后台接...

王子城 ⋅ 58分钟前 ⋅ 0

hadoop技术入门学习之发行版选择

经常会看到这样的问题:零基础学习hadoop难不难?有的人回答说:零基础学习hadoop,没有想象的那么难,也没有想象的那么容易。看到这样的答案不免觉得有些尴尬,这个问题算是白问了,因为这个...

左手的倒影 ⋅ 58分钟前 ⋅ 0

806. Number of Lines To Write String - LeetCode

Question 806. Number of Lines To Write String Solution 思路:注意一点,如果a长度为4,当前行已经用了98个单元,要另起一行。 Java实现: public int[] numberOfLines(int[] widths, Str...

yysue ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部