为何Python这么快
问题的提出是源于 这位兄弟的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]* 的形式，例如 [email]joson123@sina.com.cn[/email] [email]joson72345@sina.com.cn[/email] 的格式。
在$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>
// code by 李嘉
// 禁止任何商业目的的转载
// 不对因使用代码产生任何后果负任何责任
// 转载请保留所有声明
#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;
}
页:
[1]