海边沫沫

相濡以沫,不如相忘于江湖
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行记录的文本练练手,下面给出一个随机生成100w个email地址的小程序,写得不好,请不要见笑:
 1 #include <iostream>
 2 #include <fstream>
 3 #include <cstdlib>
 4 #include <string>
 5 #include <vector>
 6 using namespace std;
 7 
 8 int main()
 9 {
10     //创建1000个用户名
11     char letters[] = "abcdefghijklmnopqrstuvwxyz1234567890_";
12     vector<string> names;
13     for(unsigned int i=0; i<1000; i++)
14     {
15         //获取一个30以内的随机数作为用户名的长度
16         int length = rand()%30 + 1;
17         string name;
18         for(unsigned int j=0; j<length; j++){
19             int index = rand()%37;
20             name.append(1,letters[index]);
21         }
22         names.push_back(name);
23     }
24     
25     //创建700个网站名
26     string domains[] = {".com",".cn",".com.cn",".gov",".gov.cn",".net",".net.cn"};
27     vector<string> sites;
28     for(unsigned int i=0; i<100; i++)
29     {
30         //获取一个10以内的随机数作为网站名的长度
31         int length = rand()%10 + 1;
32         string name;
33         for(unsigned int j=0; j<length; j++){
34             int index = rand()%37;
35             name.append(1,letters[index]);
36         }
37         for(int k=0; k<7; k++){
38             name.append(domains[k]);
39             sites.push_back(name);
40         }
41     }
42 
43     //构建100万个email地址
44     ofstream emails("emails100w.txt");
45     for(int i=0; i<1000000; i++){
46         emails << names[rand()%1000<< "@" << sites[rand()%700<< endl;
47     }
48     
49     return 0;
50 }

Feedback

# re: 从一道简单的练习题说开去  回复  更多评论   

2007-11-14 10:27 by <a href=http://minidx.com>minidxer</a>
这里用Vector肯定效率不好的

# re: 从一道简单的练习题说开去  回复  更多评论   

2007-11-14 11:54 by ok
vector版本的emails先预分配100w大小的空间,效率应该会有所提高
emails.reserve(1000000);

# re: 从一道简单的练习题说开去  回复  更多评论   

2007-11-14 16:03 by 海边沫沫
按楼上的建议修改后,运行结果如下:
real 0m35.157s
user 0m26.005s
sys 0m9.219s

效率的提升并不大,由此可见,你说的并不是关键问题。

# re: 从一道简单的练习题说开去  回复  更多评论   

2007-11-14 16:41 by chenger
如果用非标准的散列表话,应该会更好
对付这种应用,散列表一般是最佳选择
还好0x里散列表要进标准库了

# re: 从一道简单的练习题说开去[未登录]  回复  更多评论   

2007-11-15 07:25 by Louis.G
修正下楼主的错误,堆排序并不最快,它的算法是先把小的数据放在右边然后再移到左边,两次移动的代价并不低。如果是一个有序程度较高的数组堆排序远不如快速排序,快排优化时还可在每个partition长度小的时候使用插入或冒泡以节省时间,而且划分每个partition的种子是随机选取的,可以认为它不会慢到n^2的级别。

不过像这种数据量很大的东西要效率还是自己特殊实现吧,靠标准库是不行的。过分标准的东西往往失去了特性。

# re: 从一道简单的练习题说开去  回复  更多评论   

2007-11-23 23:21 by 地狱门神
hashtable

# re: 从一道简单的练习题说开去[未登录]  回复  更多评论   

2007-11-24 10:33 by 海边沫沫
Hash table在VC++ 2005和VC++ 2008中,有hash_map、hash_set、hash_multimap、hash_multiset可用,在下一代C++标准中,它们将被更名为unordered_map和unordered_set。

用它们来去除重复项,的确很快,但是它们不能排序。

# re: 从一道简单的练习题说开去  回复  更多评论   

2007-12-04 16:44 by 新手看法
VECTOR是一块连续内存,当SIZE很大时寻址比较慢,STD::SET是HASH的话就不用多说了

# re: 从一道简单的练习题说开去  回复  更多评论   

2007-12-04 17:55 by 海边沫沫
内存大小和寻址快慢有关系吗?vector是可以随机访问的,像数组一样,寻址任何一个元素的时间花费都是常数。list是不能随机访问的,才会出现容器越大寻址越慢的情况。

std::set和std::tr1::unordered_set是不同的,它们的底层实现不同。std::set不是hash,而是红黑树。

# re: 从一道简单的练习题说开去  回复  更多评论   

2013-10-22 16:41 by booirror
生成100w个email的程序是有问题的,name.append()之后添加到vector,然后继续append,共7次,这样就不对了

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理