|
楼主 |
发表于 2004-5-7 18:58:27
|
显示全部楼层
<FONT size=3>这两个程式的大小,不再像前一个例子有那麽悬殊的差异(43 : 24,空行不计)。扣除无法删减的共同元素,例如 main() 的宣告和中间值的计算(共 13 行),两者的行数差异是 20 : 11。关键性的「输入并储存」回圈和排序动作,在 C++-style 程式中都有显着的缩短(「输入并储存」回圈的行数差异是 9 : 4,排序动作的行数差异是 9 : 1)。更重要的是,在 C++ 版本中,每一行所包含的逻辑远远简单得多 ─ 获得正确性的机会当然也就多得多。
再一次,记忆体管理在 C++-style 程式中隐喻实施;当元素以 push_back 加入,vector 便自动成长。C-style 程式则是以 realloc 做记忆体显式管理。出现在 C++-style 程式中的 vector 建构式和 push_back 函式会做掉 C-style 程式中的 malloc, realloc 动作,以及对於「被配置之记忆体大小」的追踪动作。在 C++-style 程式中,我依赖异常处理(exception handling)来记录记忆体的耗尽。在 C-style 程式中,我明白地测试以避免可能的记忆体耗尽问题。
一点也不令人惊讶,C++ 版本比较容易获得正确。我以剪贴的方式从 C-style 版本产生出这个 C++-style 版本。我忘记含入<algorithm>;我留下了 n 而忘了使用 buf.size;此外,我的编译器不支援局域( local)内的 using 指令,迫使我必须把它移到 main 之外。修正了这四个错误之後,程式就可以正确执行了。
对一个初学者而言,qsort 很是诡异。为什麽你必须给予元素个数?(因为阵列不知道它自己有多少个元素)为什麽你必须给予 double 的大小?(因为 qsort 不知道它要排序的单位是 doubles.)为什麽你必须写那个丑陋的、用来比较 doubles 数值的函式?(因为 qsort 需要一个指标指向某个函式,因为它不知道它所要排序的元素型别)为什麽 qsort 所使用的比较函式接受的是 const void* 引数而不是 char* 引数?(因为 qsort 可以对非字串的数值排序)void* 是什麽意思?前面加上 const 又是什麽意思?(唔,稍後我们再来谈这个话题)对初学者解释这些问题,恐怕很难不使他们两眼发直。相较之下解释 sort(v.begin( ), v.end()) 就容易得多:「单纯的 sort(v) 比较简单,但有时候我们想要对容器的某一部份做排序,所以更一般化的方式就是指定排序运作范围」。
为了比较效率,我首先必须决定多少笔输入才能使效率的比较饶富意义。由於 50,000 笔资料也不过是用了此程式半秒钟不到, 因此我选择以 500,000 笔输入和 5,000,000 笔输入来做比较。结果显示於表一。
表一 / 读入、排序、输出 浮点数
最佳化前 最佳化後
C++ C C/C++ 比值 C++ C C/C++ 比值
500,000 笔资料 3.5 6.1 1.74 2.5 5.1 2.04
5,000,000 笔资料 38.4 172.6 4.49 27.4 126.6 4.62
关键数字在於比值。比值大於 1 表示 C++-style 版本比较快。语言、程式库、编程风格之间的比较,众所周知十分棘手,所以请不要根据这些简单的测试就做出彻底的结论。这些比值是不同机器上数次执行结果的平均值。同一个程式的不同执行环境,其间差异低於 1 个百分比。我也执行了我这个 C-style 程式的 ISO C 严格相容版本,一如预期,其间并没有效率上的差异。
我预期 C++-style 程式会稍微快一点点。检验不同的 C++ 编译器实作品後,我发现执行结果有着令人惊讶的变化。某些时候, C-style 版本在小资料量的情况下表现优於 C++- style 版本。然而本例的重点在於,我们可以面对目前已知的技术,提供一个较高阶的抽象性和一个针对错误的较佳保护。我所使用的 C++ 编译器既普遍又便宜 ─ 不是研究室里的玩具。那些宣称可以提供更高效率的编译器,当然也适用本结果。
要找到一些人,愿意在方便性和较佳的错误防范上面付出 3, 10 或甚至 50 的比值,倒也还不罕见。但如果把这些效益放在一起,再加上两倍或四倍的速度,那就非常壮观而吸引人了。这些数字应该是一个 C++ 程式库供应商乐意接受的最小值。为了知道时间花在什麽地方,我又进行了一些额外测试(见表二)。
表二 / 读入浮点数并排序。为了解输入动作所耗费的成本,我加上一个 "generate" 函式,用来产生随机数值。
500,000 笔资料:
最佳化前 最佳化後
C++ C C/C++ 比值 C++ C C/C++ 比值
读入资料 read 2.1 2.8 1.33 2.0 2.8 1.4
产生资料 generate 0.6 0.3 0.5 0.4 0.3 0.75
读入并排序 read & sort 3.5 6.1 1.75 2.5 5.1 2.04
产生并排序 generate & sort 2.0 3.5 1.75 0.9 2.6 2.89
5,000,000 笔资料:
最佳化前 最佳化後
C++ C C/C++ 比值 C++ C C/C++ 比值
读入资料 read 21.5 29.1 1.35 21.3 28.6 1.34
产生资料 generate 7.2 4.1 0.57 5.2 3.6 0.69
读入并排序 read & sort 38.4 172.6 4.49 27.4 126.6 4.62
产生并排序 generate & sort 24.4 147.1 6.03 11.3 100.6 8.9
当然,"read" 仅仅只是读入资料,"read&sort" 仅仅只是读入资料并排序,它们都不会产生任何输出。为了对输入成本获得比较好的感觉,"generate" 用来产生随机数值,而非从输入设备读入资料。
在其他的例子和其他的编译器身上,我料想 C++ stream I/O 会比 stdio 稍稍慢一些。本程式的前一版本使用 cin 而非 file stream,情况的确如此。在某些 C++ 编译器上,档案的 I/O 确实远比 cin 快速得多,其理由至少有一部份是因为 cin 和 cout 之间的系结的拙劣处理。然而,以上数值显示,C++-style I/O 可以像 C-style I/O 一样地有效率。
如果改变这些程式,使它们读入并排序的对象是整数而非浮点数,并不会改变相对效率 ─ 虽然我们可以惊喜地发现,这种改变对 C++-style 程式而言实在非常简单(只需两个改变,C-style 程式需要 12 个改变)。这对於易维护性是一个好兆头。 "generate" 测试所呈现的差异显示出配置所花费的成本。一个 vector 加上 push_back 应该就像一个阵列加上 malloc/free 一样快,但实际却非如此。其原因是难以在最佳化过程中将「什麽事都没做的初值设定列( initializers)」的呼叫动作去除。幸运的是,配置所引发的成本,在输入(造成配置需求)所引发的成本面前,几乎总是显得渺小。至於 sort,一如预期远比 qsort 快得多,主要原因是 sort 内的比较动作是行内展开(inlines),而 qsort 必须呼叫某个函式。
实在很难选择一个例子可以好好说明效率议题。我从同事身上获得的意见是,读入并比较「数值」还不够写实,应该读入「字串」并排序。所以我写了以下程式:
#include<vector>
#include<fstream>
#include<algorithm>
#include<string>
using namespace std;
int main(int argc, char* argv[])
{
char* file = argv[2]; // 输入档的档名
char* ofile = argv[3]; // 输出档的档名
vector<string> buf;
fstream fin (file,ios::in);
string d;
while (getline (fin, d))
buf.push_back (d);
sort(buf.begin(), buf.end());
fstream fout (ofile, ios: out);
copy(buf.begin(), buf.end(),
ostream_iterator<string> (fout, "\n"));
}
我把它改写为 C 的型式,并设法让字元的读入得以最佳化。C++-style 版本执行得很好 ─ 即使是面对经过手动调整而达到最佳化效果的 C-style 版本(後者消除了字串的拷贝动作)。对於小量输出而言,没有什麽显着差异,但对於大量资料而言,sort 再一次击败了 qsort,因为其较佳的行内展开(inlines),见表三。
表三 / 读入、排序、输出 字串
C++ C C/C++
比值 C,去除
字串拷贝动作 最佳化後的
C/C++ 比值
500,000 笔资料 8.4 9.5 1.13 8.3 0.99
2,000,000 笔资料 37.4 81.3 2.17 76.1 2.03
我采用两百万笔字串,因为我没有足够的主记忆体来容纳五百万个字串而不引起分页置换(paging)。
为了知道时间花费在哪里,我也执行了刻意遗漏 sort 的程式(见表格四)。我所准备的字串相对较短(平均由七个字元构成)。
表四 / 读入并输出字串 ─ 刻意遗漏 sort
C++ C C/C++
比值 C,去除
字串拷贝动作 最佳化後的
C/C++ 比值
500,000 笔资料 2.5 3.0 1.2 2 0.8
2,000,000 笔资料 9.8 12.6 1.29 8.9 0.91
注意,string 是一个很完美的使用者自定型别,而它只不过是标准程式库的一部份而已。如果我们能够因为使用 string 而获得效率和精致,我们也能够因为使用其他使用者自定型别而获得效率和精致。
为什麽我要在编程风格和教学的文章中讨论效率呢?因为,编程风格以及我们所教导的技术,必须为真实世界的问题服务。 C++ 的创造是为了运用於大规模系统以及对效率有严格规范的系统。因此我认为,如果 C++ 的某种教育方式会导致人们所使用的编程风格和技术只在玩具程式中才有效率可言,那是令人无法 同的,那会使人们挫败并因而放弃学习。以上的量测结果显示,如果你的 C++ 风格极为依赖泛型编程(generic programming)和具象型别,以此提供更简单更达到「型别安全(type-safe)」的码,其效率可以和传统的 C 风格一较长短。类似的结果在物件导向(object-oriented)风格中也可获得。
不同的标准程式库实作品的效率表现,有戏剧性的差异,这是一个重要问题。对一个决定大量依赖标准程式库(或广为流传的非标准程式库)的程式员而言,很重要的一点是,你所采用的编程风格应该能够在不同的系统上都有至少可被接受的效率。我很惊骇地发现,我的测试程式在某个系统上,C++ style 和 C style 相比有两倍快,而在另一个系统上却只有一半快。如果系统间的变动因素超过 4,程式员就不该接受。就我所能理解,这种变异性并非由於基本因素而形成,所以不需要程式库实作者过份夸张的努力,就应该可以达到效率的一致性。采用优化程度较佳的程式库,或许是改善对标准 C++ 的认知和实际效率表现的最轻易方式。是的,编译器实作者很努力地消除各个编译器之间的微小效率差异;我估量在效率方面,标准程式库的实作者影响较大。
很明显,上述 C++-style 解法相较於 C-style 解法所带来的编程与逻辑上的简化,可以藉由 C++ 标准程式库而达到。这样的比较是否不够实在或不够公平呢?我不这麽认为。C++ 的一个关键形貌就是,它对程式库的支援能力,精致而且高效。上述简单程式所展现的种种优点,在任何应用领域中都可以保持 ─ 只要其间存在着精致而高效率的程式库。C++ 族群的挑战在於扩充领域,让一般程序员也都享受得到这些利益。也就是说,我们必须针对更多应用领域,设计并实作精致而富有效率的程式库,并让这些程式库被广泛运用。
学习 C++
即使是专业程序员,也不可能一开始就先将整个语言的全貌学习完毕,然後才开始使用它。程式语言应该要分段学习,以小型的练习来试验其种种设施。所以我们总是以分段精通的方式来学习一个语言。真正的问题不在於 "我应该先学习语言的一部份吗?" 而在於 "我应该先学习语言的哪一部份?"
关於这个问题,传统的回答是 "先学习 C++ 中与 C 相容的子集"。但是从我所思考的观点来看,这不是一个好答案。这种学习法会导致过早专注於低阶细节。它也会因为强迫学生过早面对许多技术难点而模糊了编程风格与设计上的议题,进而压抑了许多有趣的东西。本文先前的两个例子已经说明这一点。C++ 拥有较佳的程式库支援,较佳的表示法,较佳的型别检验,无疑地在在对於 "C 优先" 的作法投了一张反对票。然而,注意,我也并不是说要 "纯粹的物件导向编程风格为最优先"。我认为那又是另一种极端。
对於编程初学者而言,学习一个编程语言,应该涵盖具有实际效益的编程技术。对一个编程经验丰富但对 C++ 陌生的程式员而言,其学习应该专注於如何在 C++ 中表现具有实际效益的编程技术,以及对他自己而言崭新的技术。经验丰富的程式员所面临的最大陷阱往往在於企图以 C++ 来表现其他语言的效益。不论对初学者或有经验的程式员而言,重点都应该是观念和技术。了解 C++ 的语法和语意细节,相对於了解 C++ 所支援的设计和编程技术,是次要的。</FONT>
|
|