效率（大数加法）——《C++编程风格》读书笔记（五）

发布时间：2020-12-14 04:03:07 所属栏目：大数据来源：网络整理

导读：? 效率（大数加法）——《C++编程风格》读书笔记（五）分类：? 读书笔记2010-03-01 11:35? 1063人阅读 ? 评论(0) ? 收藏? 举报 ??? ??? C++的广泛应用要得益于它的一些底层特性，例如内联函数，它可以使我们编写出效率更高的程序。编写程序时，程序员必须知

效率（大数加法）——《C++编程风格》读书笔记（五）

分类：? 读书笔记2010-03-01 11:35? 1063人阅读? 评论(0)? 收藏? 举报

???

??? C++的广泛应用要得益于它的一些底层特性，例如内联函数，它可以使我们编写出效率更高的程序。编写程序时，程序员必须知道将主要的精力放在程序的那个部分，才能使程序的运行效率更高。例如，在程序中，如果随意创建冗余的对象，则可能会付出沉重的性能代价。在程序的源代码中，我们不一定能够看到所有的对象。例如，编译器可能会创建临时对象来作为函数参数。那些需要临时对象的语法规则将使我们难以准确地估计执行开销。因此，一些看上出不错的源代码将可能会编译成执行开销高昂的机器代码。

?? 下面是一个大数加法的例子：

[cpp]? view plain copy

#include?<iostream>??
using?namespace?std;??
class?BigInt??
{??
private:??
????char*?digits;??
????unsigned?ndigits;??
????BigInt(char?*d,unsigned?n)??
????{??
????????digits?=?d;??
????????ndigits?=?n;??
????}??
????friend?class?DigitStream;??
public:??
????BigInt(const?char*);??
????BigInt(unsigned?n?=?0);??
????BigInt(const?BigInt&);??
????void?operator=(const?BigInt&);??
????BigInt?operator+(const?BigInt&)?const;??
????void?print(FILE*?f?=?stdout)?const;??
????~BigInt()?{delete?digits;}??
};??
??
class?DigitStream??
{??
private:??
????char*?dp;??
????unsigned?nd;??
public:??
????DigitStream(const?BigInt&?n)??
????{??
????????dp?=?n.digits;??
????????nd?=?n.ndigits;??
????}??
????unsigned?operator++()??
????{??
????????if(nd?==?0)??
????????????return?0;??
????????else??
????????{??
????????????nd--;??
????????????return?*dp++;??
????????}??
????}??
};??
??
void?BigInt::print(FILE*?f)?const??
{??
????for(int?i?=?ndigits?-?1;i?>=?0;i?--)??
????????fprintf(f,"%c",digits[i]+'0');??
}??
void?BigInt::operator=(const?BigInt&?n)??
{??
????if?(this?==?&n)?return;??
????delete?[]?digits;??
????unsigned?i?=?n.ndigits;??
????digits?=?new?char[ndigits?=?i];??
????char*?p?=?digits;??
????char*?q?=?n.digits;??
????while(i--)?*p++?=?*q++;??
}??
BigInt?BigInt::operator+(const?BigInt&?n)?const??
{??
????unsigned?maxDigits?=?(ndigits?>?n.ndigits???ndigits?:?n.ndigits)?+?1;??
????char*?sumPtr?=?new?char[maxDigits];??
????BigInt?sum(sumPtr,maxDigits);//类的私有构造函数只能在类的内部使用??
????DigitStream?a(*this);??
????DigitStream?b(n);??
????unsigned?i?=?maxDigits;??
????unsigned?carry?=?0;??
????while?(i?--)???
????{??
????????*sumPtr?=?(++a)?+?(++b)?+?carry;??
????????if(*sumPtr?>=?10)??
????????{??
????????????carry?=?1;??
????????????*sumPtr?-=?10;??
????????}??
????????else?carry?=?0;??
????????sumPtr++;??
????}??
????return?sum;??
}??
??
BigInt::BigInt(unsigned?n)??
{??
????char?d[3*sizeof(unsigned)+1];//???
????char?*dp?=?d;??
????ndigits?=?0;??
????do??
????{??
????????*dp++?=?n?%?10;??
????????n?/=?10;??
????????ndigits++;????
????}?while(n?>?0);??
????digits?=?char[ndigits];??
????for(register?i?=?0;i?<?ndigits;i++)??
????????digits[i]?=?d[i];??
}??
??
BigInt::BigInt(const?BigInt&?n)??
{??
????unsigned?i?=?n.ndigits;??
????digits?=?char[ndigits?=?i];??
????char*?p?=?digits;??
????char*?q?=?n.digits;??
????while(i--)?*p++?=?*q++;??
}??
??
BigInt::BigInt(char*?digitString)??
{??
????unsigned?n?=?strlen(digitString);??
????if(n?!=?0)??
????{??
????????digits?=?char[ndigits=n];??
????????char*?p?=?digits;??
????????char*?q?=?&digitString[n];??
????????while(n--)?*p++?=?*--q?-?'0';??
????}??
????else??
????{??
????????digits?=?char[ndigits=1];??
????????digits[0]?=?0;??
????}??
}??

上述代码中的不足之处和修正：

1.??DigitStream的作用是：通过成员函数operator++从BigInt对象中连续地提取数字，并在数字全部提取完时返回零。DigitStream与BigInt非常紧密的耦合在一起，因此就成了BigInt实现的一部分。从友元关系和DigitStream的构造函数中的BigInt&类型参数，可以很清楚地看出这种耦合关系，对于简单的问题来说，DigitStream是一种昂贵的解决方案。我们只需在BigInt中使用一个私有成员函数就足够了：

[c-sharp]?

class?BigInt??

{??

//……??

char?fetch(int?i)?const?{?return?i?<?ndigits???digits[i]?:?0;}??

//……??

};??

原则：降低耦合性——将类之间的交互最小化。

2.运算符的重载不是一致和完整的。假设b是BigInt对象，而i是一个unsigned的值，程序中我们可以有b+i，但不能有i+b,这是不一致的；在BigInt中定义了+，=，但却没有定义+=，因此BigInt是不完整的。

???在用fetch()来代替DigitStream后，通过一个小小的测试，我们可以深入的分析程序的效率问题。

[cpp]? void?test()??

{??

???????BigInt?b=1;??

???????int?i?=?1；i<=1000;++i)??

???????????b=b+1;??

}??

??? 在16MHz的MC68030处理器上，这个函数需要6秒，也就是说平均每次加1运算需要6毫秒。那么这些时间都消耗在了什么地方呢？很明显b=b+1消耗了大部分的时间。在这个简单的表达式后面，大量的机器时间都被用于加法运算和赋值运算。在每次执行b=b+1时，程序都要分配4个字符串。在+右边操作数是一个整数，因此需要创建一个临时的BigInt对象来匹配operator+的参数类型，在这个临时BigInt对象的构造函数中分配了第一个字符串；然后再operator+中为sumPtr分配了第二个字符串。operator+的返回值是另一个BigInt对象，这个对象在return语句中创建，在创建对象时调用的是拷贝构造函数，并且参数就是sum。这样，在拷贝构造函数中将分配第三个字符串。最后，在operator=中将分配第四个字符串。而每个动态分配的字符串都需要被删除，因此，这就导致了在每次循环时总共需要八次内存分配器的调用。这耗费了大量的时间。

??? 通过进一步的分析，我们发现：maxDigits总是在最有意义的位置上为进位保留了一个字节的空间，即使在运算中没有发生进位时也是如此。在没有进位时，operator+将在数值的最前面增加一个零。因此，当test()中的循环结束时，在b中总共有997个零，而有意义的只是最后的四个十进制数字。程序的大部分时间都被浪费在处理含有大量零的字符串上了。

??? 另外，在BigInt中，一个逻辑状态的数值可以用多个物理状态来表示。例如数值123所对应的逻辑状态就可以由3210、321、32100等物理状态来表示。当多个物理状态对应于同一个逻辑状态时，类的设计者就必须格外小心。例如，如果我们将operator==增加到BigInt中，那个这个比较所针对的就必须是逻辑状态而不是物理状态。如果只是简单的对字符串digits进行比较，那么就会导致321不等于3210这样的情况。

??? 上面的这两个问题是由于动态字符串长度的无限增长导致的。一个简单的解决方法是：operator+在返回结果之前，对和进行规范化即可。所需的代码如下：

[cpp]? if(sum.digits[maxDigits?-?1]?==?0)??

????--sum.ndigits;??

??? 为了进一步分析程序的性能，我们可以通过对全局运算符new和delete进行重载来收集统计信息。如下，我们给出一个简单的模板类，在这个类中把统计new和delete的计数器，以及输出、重置计数器的函数都封装在一起。

[cpp]? class?HeapStats??

{??

public:??

????static?void?report(FILE?*f?=?stdout);??

????void?reset();??

private:??

????void*?operator?new(size_t);??

????void?operator?delete(void*);??

????static?int?newN;??

????int?deleteN;??

};??

int?HeapStats::newN?=?0;??

int?HeapStats::deleteN?=?0;??

void?HeapStats::report(FILE?*f)??

{??

????fprintf(f,"%d?operator?new?calls/n",newN);??

????fprintf(f,"%d?operator?delete?calls/n",deleteN);??

????fflush(f);??

}??

void?HeapStats::reset()??

{??

????newN?=?0;??

????deleteN?=?0;??

}??

void?*operator?size_t?sz)??

{??

????++HeapStats::newN;??

????return?malloc(sz);??

}??

void?operator?void*?p)??

{??

????++HeapStats::deleteN;??

????free(p);??

}??

??? 之所以我们把HeapStats类称为模板类，是因为这个类的作用与其它普通类的作用是不同的。类通常是被用来实例化对象的，而在HeapStats中只是包含了静态成员，因此用这个类来实例化对象是没有意义的。HeapStats的目的是用来收集并封装某个范围之内的静态成员。如果全局变量和非成员函数被作为类的静态成员，那么他们就可以有一个共同的标识（即这个类的名字）。模板类还可以改进程序的结构并加强封装，在大型程序中，模板类能够减少全局变量冲突的可能性。

在主程序test()前后加入下面语句：

HeapStats::reset();

test();??

HeapStats::report();

输出结果为：

4001 operator new calls

4001 operator delete calls

??? 首先，我们可以注意到程序中并没有内存泄露：对new的调用次数等于对delete的调用次数。其次，我们并没有办法来避免需要分配如此之多的字符串，但可以通过为BigInt设计一个专门的内存器来改进性能。在选择这条技术路线之前，我们可以首先对程序进行分析，看看能否在程序中减少对动态分配的字符串的需求。在目前的每次循环中，需分配4个字符串，这其中部分原因在于BigInt的实现，还有部分原因是表达式b=b+1的书写方式。

??? 在BigInt的实现中，函数operator=中的字符串分配与释放可以是不必要的。在函数中，即使旧字符串的大小等于新字符串的大小，operator=还是会分配一个新的字符串。而事实上，如果新旧字符串的大小相等，我们就不需要删除旧字符串并分配一个新字符串。下面给出了一个优化之后的operator=，如果在程序中，大多数的赋值运算都是在位数不同的数值之间进行的，那么这个优化并不会为程序带来好处。

[cpp]?

void?BigInt::operator=?(const?BigInt&?n)??

{??

????return;??

???????if?(ndigits?!=?i)//??

???????{??

?????????delete?[]?digits;??

?????????digits?=?char[i];??

???????}??

????ndigits?=?i;//??

????while?(i--)?*p++?=?*q++;??

}??

???

??? 在test()中共执行了1000次赋值运算，其中997次赋值运算中，左边操作数的位数是不用改变的，因此这个优化起到了一定的作用。

优化后运行结果为：

3004 operator new calls

3004 operator delete calls

??? 到目前，所有的修改都是针对BigInt的实现，我们也可以对客户代码test()进行修改，也是可以提高性能的。在test()中，关键语句是b=b+1，容易的，我们可以想到做下面的修改：

[cpp]? void?test()??

{??

????BigInt?b?=?1;??

????const?BigInt?one?=?1;??

????int?i?=?1;i?<=?1000;i++)??

????????b?=?b?+?one;??

}??

改后结果为：

2005 operator new calls

2005 operator delete calls

最后修改下上面提到的其它问题，优化后的程序为：

[cpp]?

#include?<iostream>??

#include<stdio.h>??

#include<stdlib.h>??

#include?<string.h>??

namespace?std;??

class?HeapStats??

{??

public:??

????FILE?*f?=?stdout);??

????void?reset();??

private:??

????size_t);??

????void*);??

????int?newN;??

????int?deleteN;??

};??

int?HeapStats::deleteN?=?0;??

FILE?*f)??

{??

????fprintf(f,newN);??

????fprintf(f,deleteN);??

????fflush(f);??

}??

void?HeapStats::reset()??

{??

????newN?=?0;??

????deleteN?=?0;??

}??

size_t?sz)??

{??

????++HeapStats::newN;??

????return?malloc(sz);??

}??

void*?p)??

{??

????++HeapStats::deleteN;??

????free(p);??

}??

class?BigInt??

{??

char*?digits;??

????unsigned?ndigits;??

????unsigned?size;//size?of?allocated?string??

????BigInt?(const?BigInt&,?const?BigInt&);??

????char?fetch?(unsigned?i)?return?i?<?ndigits???digits[i]?:?0;?}??

friend?BigInt?operator+(const?BigInt&);??

????BigInt?(char*);??

????BigInt?(unsigned?n?=?0);??

????BigInt?(const?BigInt&);??

????BigInt&?operator=?(const?BigInt&);??

????BigInt&?operator+=?(void?print?(delete?digits;}??

};??

inline?BigInt?operator+(const?BigInt&?left,?const?BigInt&?right)??

{??

????return?BigInt(left,right);??

}??

BigInt&?BigInt::operator+=(const?BigInt&?rhs)??

{??

????unsigned?max?=?1+(rhs.ndigits?>?ndigits???rhs.ndigits?:?ndigits);??

????if(size?<?max)??

????{??

????????char?*d?=?char[size?=?max];??

????????for(unsigned?i?=?0;i?<?ndigits;++i)??

????????????d[i]?=?digits[i];??

????????delete?[]?digits;??

????????digits?=?d;??

????}??

????while(ndigits?<?max)??

????????digits[ndigits++]?=?0;??

????for(unsigned?i?=?0;i?<?ndigits;++i)??

????{??

????????digits[i]?+=?rhs.fetch(i);??

????????if(digits[i]>=10)??

????????{??

????????????digits[i]?-=?10;??

????????????digits[i+1]?+=?1;??

????????}??

????}??

????if(digits[ndigits?-?1]?==0)??

????????--ndigits;??

????return?*this;??

}??

void?BigInt::print?(const??

{??

????for?(int?i?=?ndigits?-?1;?i?>=?0;?i?--)??

????????fprintf?(f,?"%c",?digits[i]?+?'0');??

}??

BigInt&?BigInt::operator=?(const?BigInt&?rhs)??

{??

????this?==?&rhs)?return?*this;??

????ndigits?=?rhs.ndigits;??

????if?(ndigits?>?size)//??

????{??

????????delete?[]?digits;??

????????digits?=?char[size?=?ndigits];??

????}??

????for(unsigned?i?=?0;i?<?ndigits;++i)??

????????digits[i]?=?rhs.digits[i];??

????this;??

}??

BigInt::BigInt(const?BigInt&?right)??

{??

????size?=?1?+?(left.ndigits?>?right.ndigits???left.ndigits?:?right.ndigits);??

????digits?=?char[size];??

????ndigits?=?left.ndigits;??

????for?(unsigned?i?=?0;i?<?ndigits;++i)??

????????digits[i]?=?left.digits[i];??

????*this?+=?right;??

}??

BigInt::BigInt?(unsigned?u)??

{??

????char?v?=?u;??

????for?(ndigits?=?1;(v/=10)?>?0;++ndigits)??

????????;??

????digits?=?char[size?=?ndigits];??

????for(unsigned?i?=?0;i?<?ndigits;++?i)??

????{??

????????digits[i]?=?u?%?10;??

????????u?/=10;??

????}??

}??

BigInt::BigInt?(const?BigInt&?copyFrom)??

{??

????size?=?ndigits?=?copyFrom.ndigits;??

????digits?=?char[size];??

????for(unsigned?i?=?0;i?<?ndigits;++i)??

????????digits[i]?=?copyFrom.digits[i];??

}??

BigInt::BigInt?(char*?digitString)??

{??

????if(digitString[0]?==?'/0')??

????????digitString?=?"0";??

????size?=?ndigits?=?strlen(digitString);??

????digits?=?for(unsigned?i?=?0;i?<?ndigits;++i)??

????????digits[i]?=?digitString[ndigits?-?1?-?i]?-?'0';??

}??

void?test()??

{??

????BigInt?b?=?1;??

????const?BigInt?one?=?1;??

????int?i?=?1;i?<=?1000;i++)??

????????b?=?b?+?one;??

}??

int?main()??

{??

????HeapStats::reset();??

????test();??

????HeapStats::report();??

????return?0;??

}??

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!