C++程序设计:原理与实践(进阶篇)16.5 数值算法-阿里云开发者社区

开发者社区> 华章出版社> 正文

C++程序设计:原理与实践(进阶篇)16.5 数值算法

简介:

16.5 数值算法


大多数的标准库算法都涉及处理数据管理问题:它们需要对数据进行拷贝、排序、查找等。但是,只有少数算法涉及数值计算。当我们需要进行计算时,这些数值算法就变得十分重要了,并且这些算法为我们在STL框架中编写数值算法提供了范例。

在STL标准库中只有四种数值算法:

数值算法

x = accumulate(b,e,i) 累加序列中的值;例如,对{a, b, c, d}计算i+a+b+c+d。结果x的类型与初始值i的类型一致

x = inner_product(b,e,b2,i) 将两个序列的对应元素相乘并将结果累加。例如,对{a, b, c, d}和{e, f, g, h}计算i+a·e+b·f+c·g+d·h。结果x的类型与初始值i的类型一致

r = partial_sum(b,e,r) 对一个序列的前n个元素进行累加,并将累加结果生成一个序列。例如,对{a, b, c, d}将生成{a, a+b, a+b+c, a+b+c+d}

r = adjacent_difference(b,e,b2,r) 对一个序列的相邻元素进行减操作,并将得到的差生成一个序列。例如,对{a, b, c, d}将生成{a, b-a, c-b, d-c}

 

这些算法可以在<numeric>中找到。我们将介绍前两个,如果你觉得有需要的话,可以自己去查阅其他两个的详细情况。

16.5.1 累积

accumulate()是最简单但最有用的数值算法。在其最简单的形式中,该算法将一个序列中的值进行累加:

 

给定初始值init,该算法将序列[f?irst:last)中的每个值加到init上,并将和返回。init通常被称为累加器。例如:

 

这段代码将打印15,即0+1+2+3+4+5(0是初始值)。显然,accumulate()能够被用于所有类型的序列:

 

结果(和)的类型与accumulate()用来保存累加器的变量的类型一致。这带来了一定的灵活性,这可能是十分重要的,例如:

 

在一些计算机上long的有效位数要比int更多。与int型相比,double能够表示更大范围的数,但可能精度更差。我们将在第24章中再讨论范围和精度在数值计算中所起的作用。

将保存结果的变量用作初始值是一种常见的指明累加器类型的方法:

 

记住:要初始化累加器并将accumulate()的结果保存在这个变量中。在本例中,s2在初始化之前就用作了初始化器,因此算法的结果是未定义的。我们将s3传递给accumulate()(传值方式,参见8.5.3节),但算法结果并未被保存,这只是浪费时间。

16.5.2 泛化accumulate()

基本的三参数accumulate()版本执行累加运算。但是,我们可能还想在序列上执行很多其他有用的运算,例如乘法和减法。为此,STL提供了另一个四参数的accumulate()版本,允许我们指定要执行的运算:

 

任何接受两个累加器类型实参的操作均能用于这一版本的accumulate()。例如:

 

这段代码将打印35.1384,即1.0×1.1×2.2×3.3×4.4(1.0为初始值)。这里提供的二元运算符multiplies<double>()是一个实现乘法运算的标准库函数对象;multiplies<double>实现double的乘法;multiplies<int>实现int的乘法,等等。还有一些其他的二元函数对象:plus(加法),minus(减法),divides,modulus(取余)。这些对象均在<functional>中定义(见附录C.6.2)。

注意,为了计算浮点数的积,初始值显然应设为1.0。

如sort()例子(见16.4.2节)中所示,我们常常对类对象中包含的数据更感兴趣,而不仅仅是普通内置类型。例如,给定物品的单位价格和单位数,我们可能想要计算所有物品的价值总和:

 

我们可以让accumulate的运算符从一个Record元素中抽取units,将其与单位价格相乘并加到累加器中:

 

我们在这里很“懒惰”,使用了函数而不是函数对象——这仅仅是为了展示可以这么做。我们倾向于优先选用函数对象:

如果需要在调用之间保存值;

或者,如果代码很短以致内联化会带来很大不同(至多是几个原语操作)。

基于第二个原因,我们应该在本例中选用函数对象。

试一试

定义一个vector<Record>,用你所选择物品的四个记录将其初始化,并用上面的函数计算物品的总价值。

16.5.3 内积

给定两个向量,将它们对应位置的元素相乘并将结果累加,这一运算称为向量的内积(inner product),内积在很多领域都十分有用(例如物理和线性代数,参见24.6节)。如果你更喜欢代码而不是文字,下面就是STL版本:

 

这段代码将内积的概念推广到任意元素类型的任何序列。以股票市场指数为例。在股票市场中,每一上市公司都会被分配一个“权重”。例如,在道琼斯工业指数中,我们看到Alcoa公司的最新权重为2.4808。为了获得当前的指数值,我们将每个公司的股票价格与其权重相乘,并将所得所有加权价格相加。显然,这就是价值和权重的内积。例如:

 

 

注意,inner_product()处理两个序列。但它只接受三个参数,对于第二个序列只描述了开始位置。算法假设第二个序列包含的元素个数要等于或多于第一个序列。如果这一假设不成立,将产生运行时错误。对于inner_product()而言,第二个序列包含更多元素是没问题的,那些“多余的元素”将简单地不予处理。

两个序列不需要具有相同的类型,元素类型也不必相同。为了展示这一点,我们使用了vector存储价格、用list存储权重。

16.5.4 泛化inner_product()

inner_product()可以像accumulate()那样泛化,但它需要两个额外参数:一个用于将累加器与新值组合起来(与accumulate()完全一样),另一个用于组合元素值对:

 

在16.6.3节中,我们将回到道琼斯的例子,给出一个更优雅的解决方案,其中就使用了这个泛化的inner_product()。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:

华章出版社

官方博客
官网链接