C++博客-Simple is beautifull-最新评论

re: 为什么Python的性能比较好呢？

christanxw — Sat, 01 Apr 2006 14:10:00 GMT

#include
#include
#include

unsigned long cryptTable[0x500];
const int HASH = 0;
const int HASH_A = 1;
const int HASH_B = 2;

void InitCryptTable()
{
unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;
for(index1 = 0; index1 < 0x100; index1++)
{
for(index2 = index1, i = 0; i < 5; i++, index2 += 0x100)
{
unsigned long temp1, temp2;
seed = (seed * 125 + 3) % 0x2AAAAB;
temp1 = (seed & 0xFFFF) << 0x10;
seed = (seed * 125 + 3) % 0x2AAAAB;
temp2 = (seed & 0xFFFF);
cryptTable[index2] = (temp1 | temp2);
}
}
}

unsigned long Hash(char *pStr, unsigned long dwHashType)
{
unsigned char *key = (unsigned char *)pStr;
unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
int ch;

while(*key != 0)
{
ch = toupper(*key++);

seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
}
return seed1;
}

struct HashItem
{
unsigned long m_nHashKeyA;
unsigned long m_nHashKeyB;
bool m_bExist;
};

int main()
{
__int64 t1, t2;
GetSystemTimeAsFileTime( (LPFILETIME)&t1 );

InitCryptTable();
FILE* fread = fopen("c:\\email.txt","r");
FILE* fwrite = fopen("c:\\emailnew.txt","w+");

HashItem *hashTable = new HashItem[780000];

char line[256] = "";
fgets(line,255,fread);
while(!feof(fread))
{
int nStart = Hash(line,HASH) % 780000;
int nPos = nStart;
if(!(hashTable[nPos].m_bExist
&& hashTable[nPos].m_nHashKeyA ==Hash(line,HASH_A)
&& hashTable[nPos].m_nHashKeyB == Hash(line,HASH_B)))
{
hashTable[nPos].m_nHashKeyA = Hash(line,HASH_A);
hashTable[nPos].m_nHashKeyB = Hash(line,HASH_B);
hashTable[nPos].m_bExist = true;
fprintf(fwrite,"%s",line);
}

fgets(line,255,fread);
}

GetSystemTimeAsFileTime( (LPFILETIME)&t2 );
printf( "经过了%I64d.%04I64d毫秒\n", (t2-t1)/10000, (t2-t1)%10000 );
fclose(fread);
fclose(fwrite);
delete [] hashTable;

std::cin.get();
}

耗时343毫秒。很不错了。呵呵。Ptyong也是C写出来的，C/C++效率是完全可以比Pyton更快的，就看怎么实现算法了。在总多的脚本语言中Python是比较慢的一个了。

christanxw 2006-04-01 22:10 发表评论

re: 为什么Python的性能比较好呢？

铏瓙 — Fri, 31 Mar 2006 10:24:00 GMT

2. 参看Python代码实现的实现
#include

// code by 李嘉
// 禁止任何商业目的的转载
// 不对因使用代码产生任何后果负任何责任
// 转载请保留所有声明

#include
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;
}

from link：
http://blog.csdn.net/imjj/archive/2006/03/31/645163.aspx?Pending=true

铏瓙 2006-03-31 18:24 发表评论

re: 为什么Python的性能比较好呢？

虫子 — Fri, 31 Mar 2006 10:23:00 GMT

为了方便日后查看（怕那些链接无效了），特意把一些其他实现的代码摘录下来：
====================================================1.Python的原始实现：
#remove duplicated email address from file
import datetime
if __name__ == "__main__":
t = datetime.datetime(2000,1,1)
print str(t.today())
hashtable = {}
f = file("email.txt","r")
f2 = file("email_new.txt","w")
line = f.readline();
while len(line)>0:
if not hashtable.has_key(line):
hashtable[line] = 1
f2.write(line)
line = f.readline();
f.close()
f2.close()
t2 = datetime.datetime(2000,1,1)
print str(t2.today())

from link：
http://blog.vckbase.com/jzhang/archive/2006/03/28/18807.html
====================================================

虫子 2006-03-31 18:23 发表评论