快速URL排重的方法(二)

接上篇，起初我为了输入输出方便，是用perl去实现的，后来发现perl中求模速度太慢，就改用C了

常量定义：SPACE指你要分配多大的内存空间，我这里是为5000万数据的每一条分配4字节

constintSPACE=50000000*4;
constintMAXNUM=SPACE*8;
#defineLINE_MAX2048
intbits[]={0x1,0x2,0x4,0x8,16,32,64,128};
char*db=NULL;

主程序：这里循环读入标准输入的每一行，进行排重。

intmain(intargc,char*argv[])
{
db=newchar[SPACE];
memset(db,0,SPACE);
charline[LINE_MAX];
while(fgets(line,LINE_MAX,stdin)!=NULL){
intlen=strlen(line);
len--;
if(len<=0)continue;
if(!is_exist(line,len)){
//addcodehere
}
}
return0;
}

判定函数：我没有做Bloom filter算法中描述的10次hash，而是做了一个MD5，一个SHA1，然后折合成9次hash。

boolis_exist(constchar*str,intlen){
unsignedinthashs[9];
unsignedcharbuf[20];
MD5(str,len,buf);
memcpy(hashs,buf,16);
SHA1(str,len,buf);
memcpy(hashs+4,buf,20);
intk=0;
for(intj=0;j<sizeof(hashs)/sizeof(hashs[0]);j++){
intbitnum=hashs[j]%MAXNUM;
intd=bitnum/8;
intb=bitnum%8;
charbyte=db[d];
if(byte&bits[b]==bits[b]){
}else{
byte|=bits[b];
db[d]=byte;
k++;
}
}
return(k==0);
}

主要算法就在这里了，实际应用的话可以采用循环监视磁盘文件的方法来读入排重数据，那些代码就与操作系统相关，没必要在这写了