现在的位置: 首页 > 综合 > 正文

[zz]c++有时比Python慢

2013年09月14日 ⁄ 综合 ⁄ 共 7172字 ⁄ 字号 小 中 大 ⁄ 评论关闭

原文地址：

http://student.csdn.net/space.php?uid=112600&do=blog&id=14316

 

 

 

部门最近在搞JVM上的动态语言，比如Groovy。在享受了动态语言的种种灵活之后，性能自然而然被拿出来PK。

然后玩Python的同事就旧事重提，从网上找来一段Python代码，很多Python的人都知道了，很多C++的人也知道了，它跑得很快。

为了让文章好看一点，我来编一个故事，说，有个软件公司，正要招刚从大学毕业的C++程序员和Python程序，面试题是同一道：

      有一个15万行的文档，其中很多行的内容相同的，请写一段代码，读入这文件，尽可能快地将不重复的行内容输出到新文件，注意次序不要改变”，比如，有5行内容：

B1

B2

A2

B2

B1

要求新文件内容为：

B1

B2

A2

 

小P新学习Pythont不久，他写出代码如下：

Code:
  1. import time  
  2. if __name__ == "__main__" :  
  3.     beg = time.time()  
  4.     hashtable = {}  
  5.     fi = file("test.txt", "r")  
  6.     fo = file("test_dst.txt", "w")  
  7.   
  8.     count = 0;  
  9.     for line in fi :  
  10.         if not hashtable.has_key(line) :  
  11.             hashtable[line] = 1  
  12.             fo.write(line)  
  13.             count = count +1  
  14.   
  15.     fo.close()  
  16.     fi.close()  
  17.   
  18.     end = time.time()  
  19.       
  20.     print "count=", count, "time=", (end - beg)*1000, "ms"  

这是一段中规中矩的Pythont程序，符合Python的风格：看不出是新手还是老手写的。:)

OK，在我的机器上，我准备了一个15万文字，但不重复行只有4万行的文件，上面的代码运行时间是281 毫秒。性能比一会儿的相同逻辑的C++代码还要快，所以小P被相中了。

 

接来是C++的面试。 嗯，不懂 hash的同学可能要被抛弃了，用vector,list的都会非常非常的慢，或许用map的人可以考虑，理由是严格地讲STL里是没有hash数据结构的。但反过来说，有在学校里认真学习数据结构，并且有实际使用STL的C++程序员，应该都知道几乎所有版本的STL实作，都有附加实现了hash——再者，还是从性能上，用map也还是很慢很慢，你应该知道在find上，它的复杂度和hash表是什么倍数。

还好，故事中的小C，他虽然学习C++也不久，但他懂hash，也写了一段中规中矩的代码：

Code:
  1. #include <iostream>  
  2. #include <string>  
  3. #include <fstream>  
  4. #include <sstream>  
  5. #include <ctime> //for clock()  
  6. #include <ext/hash_map>  
  7.   
  8. using namespace std;  
  9. using namespace __gnu_cxx;  
  10.   
  11. struct string_hash  
  12. {  
  13.     size_t operator()(const string& str) const  
  14.     {  
  15.         return __stl_hash_string(str.c_str());  
  16.     }  
  17. };  
  18.   
  19. struct string_compare  
  20. {  
  21.     bool operator () (string const& str1, string const& str2)  
  22.     {  
  23.         return str1 == str2;  
  24.     }  
  25. };  
  26.   
  27. int main()  
  28. {  
  29.     clock_t beg = clock();  
  30.   
  31.     hash_map<string, int, string_hash, string_compare> hastable;  
  32.   
  33.     ifstream fi ("test.txt");  
  34.     ofstream fo ("test_dst.txt");  
  35.       
  36.     string line;  
  37.     size_t count = 0;  
  38.       
  39.     for (getline(fi, line); !fi.eof(); getline(fi, line))  
  40.     {  
  41.         if (hastable.find(line) == hastable.end())  
  42.         {  
  43.             hastable[line] = 1;   
  44.             fo << line << endl;  
  45.             ++count;  
  46.         }  
  47.     }  
  48.       
  49.     fo.close();  
  50.     fi.close();  
  51.       
  52.     clock_t end = clock();  
  53.     cout << "count = " << count << ", time = " << (end-beg) << "ms" << endl;  
  54.   
  55.     return 0;  
  56. }  

写的代码和python版本相比，似乎长了点，但其实逻辑一致，得分应该和小P差不多，但我们现在，正在挣扎，要不要小C呢！为什么?因为同样作为初学者，同样一道题，作为一个C++的程序员，他写这道题，性能比Python那个版本，要来得差呢！我们把他的代码编译为速度优化版本，相同测试条件，连续跑了10次，最慢的要1秒多，最快也就600毫秒。远远比不上Python那个版本的281毫秒。如果要说优化，我们知道，用上PSYCO，代码基本上一行不改，就可再提速近100毫秒……

要拒掉小C，说他什么好？有人说，怪他不懂得使用API的优势，可以直接调用Windows API 的文件映射等技术，也可以不使用__stl_hash_string 这个由STL提供的字符串生成hash值的算法（埋怨人家小C数学学得不太好？）；还可以埋怨他偷懒使用C++扩展库hash容器，其实只要1千行左右吧，应该可以写得了同个更高插入的查找性能的哈希表……（见此）

是的，这就是C++语言，我很不喜欢的某种“哲学”，高手总是可以有各种牛逼哄哄的手段，来写出相当不一般的，相当可以和初学者拉开令人“敬佩”的距离……

这可不是我喜欢的！ 如果C++语言的学习，就是非得把一个初学者变成一个专家（，然后他才算入了门） 就已经够雷人了，那在库的使用上，我真不想逼着每个人都精通这个算法那个算法，都精通无数个库，都精通Windows或Linux那无数个API——哈哈，其这我也不是真正的教育家，这样说得有些沉重了。

真正的事实通常是这样，我，一个主要用C++的程序员，和我的那位玩Python的同事（他在工作中基本上不编程），下班后喝点小酒，然后扯到这件性能PK的事来，你说，我出手拿出一段数百，甚至上千行的代码，去PK人家的简洁优雅的20行代码。我这哪好意思嘛，简直就是未经先乱了阵脚。再者，人家的代码拿到linux下一回车，就能执行，你说我好意思还要在千行代码，非常wei suo地藏了几行Windows的API调用吗？

输就输了，但还是要在可接受的范围内，做点优化——Python俺也不是完全不懂，动态语言的一些内幕，我也略知一二的说。呵呵。这个可接受的范围，我约定的是，一不调用特定的操作系统的API，二是在C++环境内搞定。

Code:
  1. int main()  
  2. {  
  3.     clock_t beg = clock();  
  4.    
  5.     //优化一：给hastable预设一个足够大的数目  
  6.     hash_map<string, int, string_hash, string_compare> hastable(40050);  
  7.    
  8.     ifstream fi ("test.txt");  
  9.     istringstream ssi;  
  10.       
  11.     fi.seekg(0, ifstream::end);  
  12.     size_t fileSize = fi.tellg();  
  13.     fi.seekg(0);  
  14.           
  15.     //优化二：一次读入文件的全部内容到内存  
  16.     char* buf = new char[fileSize];  
  17.     fi.read(buf, fileSize);   
  18.       
  19.     //优化三：从存有数据的那段内存，直接构造出"内存流", 避免复制  
  20.     ssi.rdbuf()->pubsetbuf(buf, fi.gcount());  
  21.     fi.close();   
  22.       
  23.     string line;  
  24.     size_t count = 0;  
  25.   
  26.     ostringstream sso;  
  27.       
  28.     //优化四：从内存流读每一行，而不是从文件流  
  29.     for(getline(ssi, line); !ssi.eof(); getline(ssi, line))  
  30.     {  
  31.         if (hastable.find(line) == hastable.end())  
  32.         {  
  33.             hastable[line] = 1;   
  34.             //优化五：先输出到内存流，而不是到文件流  
  35.             sso << line << endl;  
  36.             ++count;  
  37.         }  
  38.     }  
  39.     delete [] buf;  
  40.       
  41.     ofstream fo ("test_dst.txt");  
  42.     fo << sso.str() << endl;  
  43.     fo.close();  
  44.       
  45.     clock_t end = clock();  
  46.     cout << "count = " << count << ", time = " << (end - beg) << "ms" << endl;  
  47.   
  48.     return 0;  
  49. }  

     取文件大小，没有考虑超过2G的文件，我想在本“面试”中，是可以接受的。另一处要推敲的是，clock_t在linux下，会大很多，可以通过一个CLOCK_PER_SEC(?)宏解决，这里略。

    1. 预定hash表个数

     哈希表上来就先预定4万多个（差不多就是受测文件内容不同的行数），这有点赖皮呵呵。（或许你的hash没这功能）

     2.一次读入文件全部内容

      一次性读入文件，这可以理直气壮，估计py的C语言实现，也会玩这个。

      3. 将内存直接变成"流"

     读入内存后，通过“pubsetbuf” 函数，直接将它变成一个流(stringstream)，这也是必然的，可以避免一次大内存申请，更主要是是内存复制。我相信对于多数语言，甚至同样是静态的Java语言，这都是此类需求的必然的实现方法。

     4. 从内存流读，而不是从文件流

     这也是第3步的目标。

      5. 先输出到内存，最后再一次输出成文件。

      这应该是最先想到的，而且效果可能也是最好的一个。

       ----------------------------------

      就这样，还是比python慢：最快时是296秒。几个千分之一秒的差距嘛，呵呵……同事要祭出Psyco了。

 

      我该怎么办呢？没事，我可以说，输赢不是目的，互相学习，理解不同语言间的机制，才是重要的——有点官腔的说——这样说吧，我的C++水平很一般……会有人有更漂亮而优雅的优化的。

        -补充：-----------最后的优化：升级编译器 :) ----------------------------------------------------------

       下面评论中有网友说，他只是优化了读写IO，用的是tr1（Technical Report 1，有待以后正式加入）下的hash_map，速度很是快了些了。非常感谢他的提醒，我们不妨试试同样是简单的（我不准备在这个小游戏上，大动干戈地改代码），但有效的性能优化之最后招数：我的Python同事有Psyco不可怕，我们坐着就可以享受编译器的升级。

        我想起我用的编译器是非常古老mingw32-gcc3.4.5，费点劲，从网上下载了新版装上（4.4.0，好像也不是最新的gcc）。

        一行代码不改，从296，直接提升为187 :) 好，现在C++完胜未优化版本的Python代码，可以和Psyco的版本比比了。

       --------------------------------------------------------------------

       最主要的是，性能和优雅，有时候后者更重要，不然的话，我也不会跟着玩了python这么些年，它性能差的地方，可多了。但它真的优雅。直到我发现，其实 除非逼急了，否则C++ 你也可以一直用得很优雅。而且优雅不是个人的事，当一个团队的人都保持优雅了，事情就美妙了。

       换一句通俗的原则：千万别一开始就想着性能优化的事，所以，小C我们要了。

 

 

 

 

 

 

PS:

hash_map在vs下使用和在gcc下使用是有差异的，如下：

1.vs中：

#include <hash_map>

// 注意头文件和namespace

using namespace stdext;

int main()

{

hash_map<string, int> hmap;

 return 0;

}

 

2.gcc下：

#include <ext/hash_map>

using namespace __gnu_cxx;

// 需要自己写hash函数
struct string_hash

{

     size_t operator()(const string& str) const

     {

           return __stl_hash_string(str.c_str());
     }
};
int main()
{

hash_map<string, int, string_hash> hmap;
return 0;

}

 

 

另外，在vs中使用hash_map还要特别注意待哈希对象的hash函数和comp函数的定义形式。

举个例子，对于我的自定义类型

typedef struct  StatusNode
{
    int data[3];
    StatusNode* next;
    StatusNode* parent;
}StatusNode,StatusList;

 

在gcc下，我们对StatusNode作hash所作的工作如下：

struct SN_hash
{
    size_t operator()(const StatusNode& sn) const
    {
        return sn.data[0]+sn.data[1]*100+sn.data[2]*10000;
    };
};

struct SN_comp
{
    bool operator()(const StatusNode& sn1,const StatusNode& sn2) const
    {
        return (sn1.data[0]+sn1.data[1]*100+sn1.data[2]*10000)==(sn2.data[0]+sn2.data[1]*100+sn2.data[2]*10000);
    };
};

 

然后

hash_map<StatusNode, int, SN_hash, SN_comp> hmap;

即可正常使用

 

 

但在vs下，你会发现这种作法是行不通的，取而代之的方法如下：(hash函数和comp函数定义在同一个struct中)

struct SN_hashmap
{
    static   const   size_t   bucket_size   =   4;  
    static   const   size_t   min_buckets   =   8;  
    size_t operator()(const StatusNode& sn) const
    {
        return size_t(sn.data[0]+sn.data[1]*100+sn.data[2]*10000);
    }
    bool operator()(const StatusNode& sn1,const StatusNode& sn2) const
    {
        return (sn1.data[0]+sn1.data[1]*100+sn1.data[2]*10000)==(sn2.data[0]+sn2.data[1]*100+sn2.data[2]*10000);
    }
};

然后

hash_map<StatusNode, int, SN_hashmap> hmap;

使用

 

 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞