海边沫沫

相濡以沫,不如相忘于江湖
posts - 9, comments - 113, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理
俗话说得好:“光说不练是假把式。”学习C++也是这样,无论看再多的书,如果不自己动手练一练,是体会不到C++的真谛的。在这里,我给自己找了一个简单的练习题:

有一个文本文件,其中保存了100万条email地址的纪录,每一条记录为一行,要求对这个文件中的记录进行排序,并去除重复的项,结果写入另外一个文件。

经常逛CSDN的朋友对这个题目肯定不陌生,因为在CSDN上就曾经有一个讨论是C++更快还是Python更快的帖子,使用的测试题就是这样的,不过他们使用的记录只有78万条,我这里只是增加到了100万条而已。

现代C++的观点更以前相比已经发生了转变,效率已经不是最重要的考虑因素了,最重要的是怎样更快更正确的编写程序,这一点通过《C++ Primer》第四版和第三版的比较就可以看出来。在第四版中,作者更加偏重于介绍STL中的vector和bitset,而不再是数组指针和位操作符;更加偏重于std::string而不是char * ,虽然对于某些在效率方面的要求有些偏执狂的人来说,std::string的实现并不是最完美的。

因此,使用标准库来完成这个题目是很简单的,代码如下:
 1 #include <iostream>
 2 #include <fstream>
 3 #include <vector>
 4 #include <string>
 5 #include <algorithm>
 6 
 7 int main()
 8 {
 9     //读取文件中的email地址到vector中
10     std::ifstream input_file("emails100w.txt");
11     std::string tmp;
12     std::vector<std::string> emails;
13     while(input_file >> tmp)
14     {
15         emails.push_back(tmp);
16     }
17     
18     //排序
19     std::sort(emails.begin(),emails.end());
20     
21     //去除重复项
22     std::vector<std::string>::iterator end_after_unique = std::unique(emails.begin(),emails.end());
23     
24     //写入结果文件
25     std::ofstream output_file("results.txt");
26     for(std::vector<std::string>::iterator it = emails.begin(); it != end_after_unique; it++)
27     {
28         output_file << *it << std::endl;
29     }
30     
31     return 0;
32 }

加上注释和程序中的空行,也只需要32行代码。使用标准库的好处是显而易见的,整个程序的意义都非常清晰,而且不容易出错,使用STL真的是太方便了。那么,运行效率如何呢?我使用Linux中自带的time命令对程序的运行时间进行分析,如下:
$ time ./SortAndUnique

real 0m35.786s
user 0m26.613s
sys  0m9.437s

那么,STL中的容器还有别的可以完成这个任务吗?我想到了std::set,该容器在插入数据的时候,会自动抛弃重复的值,而且它里面的内容都是排好序的,这么看来,这个容器更加适合于我们的任务。那么,写个代码试一下:
 1 #include <iostream>
 2 #include <fstream>
 3 #include <set>
 4 #include <string>
 5 #include <algorithm>
 6 
 7 int main()
 8 {
 9     //读取文件中的email地址到std::set中
10     std::ifstream input_file("emails100w.txt");
11     std::string tmp;
12     std::set<std::string> emails;
13     while(input_file >> tmp)
14     {
15         emails.insert(tmp);
16     }
17     
18     //写入结果文件
19     std::ofstream output_file("results.txt");
20     for(std::set<std::string>::iterator it = emails.begin(); it != emails.end(); it++)
21     {
22         output_file << *it << std::endl;
23     }
24     
25     return 0;
26 }

嗯,不错,这个代码的行数更少。那它的运行效率呢?比使用std::vector的那个版本是快些还是慢些呢?请看下面的测试数据:
$ time ./SortWithSet

real 0m21.544s
user 0m12.370s
sys 0m9.609s

哇塞,这个程序比前一个整整快了14秒多,其中sys的时间是差不多的,说明这两个版本在输入输出的操作上没多大区别,而排序和去除重复项的工作,使用std::set只有使用std::vector一半不到的时间。

为什么会这样?我认为主要有以下几个原因:

1、std::sort算法使用的排序方法我们不清楚,我们知道,排序有很多种方法,如简单排序、快速排序、堆排序等,简单排序是最慢的,它的时间复杂度为O(n2) ,而快速排序呢,它在最好情况下能达到O(n*log2n),而最坏情况下就只有O(n2)了,堆排序速度最快,时间复杂度为O(n*log2n)。我不知道std::sort算法使用的是不是堆排序,但是我可以肯定它绝对不会使用简单排序,编写STL的人可不会那么笨。而std::set使用的是什么数据结构呢?一般都是使用的红黑树(平衡二叉树、AVL树),使用该结构的特点是查找一个元素的时间复杂度绝对不会超过log2n+1,因此,使用std::set进行排序,它的时间复杂度肯定是O(n*log2n)了。另外,在C++ 0x标准中,会加入另外一些标准容器,如std::unordered_set,从名字上可以看出,它是一个没有排序的set,它使用的数据结构就是哈希表,虽然没有排序,但是它查找数据的时间复杂度却是一个常数。

2、使用std::set容器减少了std::string的复制次数,我们知道STL的容器中保存的是我们的数据的副本,因此,将std::string对象放到std::vector容器中的时侯,会发生一个复制操作,而在使用std::sort算法的时候,容器中的元素交换位置,又会发生很多次的复制操作,再使用std::unique算法的时候,移动容器中的元素也要发生复制操作。使用std::set容器,它只在insert的时候复制一次而已。所以,使用std::set的这个版本比较快那是理所当然的了。

当然,如果你不使用std::string而是用char *,不使用容器和算法而是自己实现平衡二叉树,当然可以写出更快的版本,不过要付出更多的调试代价。

最后,为了让大家都能够找个100w行记录的文本练练手,下面给出一个随机生