向东博客 专注WEB应用 构架之美 --- 构架之美，在于尽态极妍 | 应用之美，在于药到病除|赢在IT，Playin' with IT,Focus on Killer Application,Marketing Meets Technology.

问题的提出是源于 这位兄弟的BLOG，在他的这个实现中，Python具有相当不错的性能，不但优于帖子中的C实现性能，也优于随后的跟贴中众多的C++实现的性能。

在经过了多次尝试，我还是很难找出一个优于Python性能的实现。这不是一件正常的事情，Python的性能注定不会优于C/C++，这是因为Python是解释执行的，解释的过程必然会消耗CPU时间，所以我查阅了Python的源码试图找出为何Python对于这个任务有如此好的性能的原因。

任务描述如下

对于一个78W行的文本文件，每一行是一个Email地址，文件中存在有重复的行，任务的要求是尽可能快的从这个文本文件生成一个无重复的Email的文本文件

一些相关的实现，可以参看这个地址
有如下的三个问题需要注意

对于这种大量的字符串比较，直接使用字符串比较函数是严重妨碍性能的
IO性能是要注意的
尽可能的少使用占用内存
在我的尝试中，发现重复调用 ofstream::operator<< 是比较影响性能的，而使用 fprintf或使用copy 等 STL 算法输出到则性能好的多。使用一种好的Hash算法是影响程序性能的关键。任务中的EMail字符串总是具有[a-z]*[0-9]*@([a-z]*\.)+[a-z]* 的形式，例如 joson123@sina.com.cn joson72345@sina.com.cn 的格式。

在$PySrc/Objects/dictobject.c 中，对Python的Hash机制作了一些描述，总的来说，Python的Hash机制对于这种连续型的字符串有相当好的离散度，对于这个 78W 例子，python_hash() % 780000能够很均匀的分散到各个值，最大的冲突数为 8。 以下是按照类似 Python的 Hash算法实现的 C++ 版本的结果

E:\Workspace\Temp\Email>my 经过了1687.5000毫秒 E:\Workspace\Temp\Email>my 经过了1718.7500毫秒 E:\Workspace\Temp\Email>my 经过了1671.8750毫秒 E:\Workspace\Temp\Email>my 经过了1656.2500毫秒 E:\Workspace\Temp\Email>py_email.py 2.82014641526 E:\Workspace\Temp\Email>py_email.py 2.74879181572 E:\Workspace\Temp\Email>py_email.py 2.76348586203 E:\Workspace\Temp\Email>dir *.txt 2006-03-28  13:09        19,388,869 email.txt 2006-03-29  22:51        17,779,266 email_new.txt (py_email.py 写出) 2006-03-29  22:50        17,779,266 email_new_my.txt (my.exe 写出)
py_email.py 的实现参看这里 my.cpp 实现如下 使用 cl /O2 /EHsc /D_CRT_SECURE_NO_DEPRECATE my.cpp 编译
#include <cstdio> #include <windows.h>  using namespace std; #define c_mul(a, b) (a * b & 0xFFFFFFFF) size_t python_hash(const char * str) {   size_t value = str[0] << 7;   size_t len = 0;   while(*str != 0)   {     value = c_mul(1000003, value) ^ *str++;     len++;   }   value = value ^ len;   if (value == (size_t)-1)   value = (size_t)-2;   return value; } size_t hash(const char * str, size_t seed = 1) {   size_t h = 0, g;    size_t len = 0;   while (*str)  {      h = (h << 4) + *str++;      if ((g = (h & 0xF0000000))) {        h = h ^ (g >> 24);        h = h ^ g;        h = h ^ seed;     }      len++;   }    return h;  } #define MAX_TABLE_SIZE (780000) #define MAX_CONFI 9 struct hash_item {   size_t items[MAX_CONFI];   size_t item_count;   hash_item()   {     item_count = 0;   }   bool check_has(const char * str)   {     size_t key = hash(str);     for(size_t i = 0; i < item_count; i++)     {       if (items[i] == key)       return true;     }     items[item_count++] = key;     return false;   } }; int main( void ) {   __int64 t1, t2;   GetSystemTimeAsFileTime( (LPFILETIME)&t1 );   FILE * fin = fopen("email.txt", "r");   FILE * fout = fopen("email_new_my.txt", "w+");   size_t hash_key_a = 0;   size_t hash_key_b = 0;   size_t pos_x = 0;   size_t pos_y = 0;   const char * buffer = NULL;   char line[255];   fgets(line, 255, fin);   hash_item * table = new hash_item[MAX_TABLE_SIZE];   while(!feof(fin))   {     buffer = line;     hash_key_a = python_hash(buffer);     pos_x = hash_key_a % MAX_TABLE_SIZE;     if (!table[pos_x].check_has(buffer))       fprintf(fout, "%s", buffer);       fgets(line, 255, fin);   }   GetSystemTimeAsFileTime( (LPFILETIME)&t2 );   printf( "经过了%I64d.%04I64d毫秒\n", (t2-t1)/10000, (t2-t1)%10000 );   fclose(fin);   fclose(fout);   delete [] table; }


[url=http://wiki.woodpecker.org.cn/moin/BPUG]啄木鸟Python开源社区 [/url]

作者：jackxiang@向东博客 专注WEB应用 构架之美 --- 构架之美，在于尽态极妍 | 应用之美，在于药到病除
地址：http://jackxiang.com/post/663/
版权所有。转载时必须以链接形式注明作者和原始出处及本声明！