方案一:直接使用STL map

方案二:取模分组再使用STL map

方案三:直接使用取模哈希

方案四:链式哈希表

下面统计了各种方案在 5*106级别的用时(ubuntu, 无O2优化, 3.30GHz)及判重错误的数据量(数据随机生成)

Insert:
STL Map Use Time:4490ms
HASH + Map Use Time:1245ms
Origin Hash Use Time:67ms
List Hash Use Time:728ms
Read:
STL Map Use Time:5812ms, 0 Mistakes
HASH + Map Use Time:1983ms , 0 Mistakes
Origin Hash Use Time:58ms , 4847252 Mistakes
List Hash Use Time:407ms , 0 Mistakes

部分代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <ctime>
#include <vector>

#define MX 5000001
#define MY 10001
#define MD 1423333

using namespace std;

map<int,int> origin;
map<int,int> origin_plus[MX];
int origin_hash[MX];
vector<int> list_hash[MD+1];

inline void insrt1(int x){
    origin[x]=x;
}

inline void insrt2(int x){
    origin_plus[x%MD][x]=x;
}

inline void insrt3(int x){
    origin_hash[x%MD]=x;
}

inline void insrt4(int x){
    int mx=x%MD;
    for(register unsigned int j=0; j<list_hash[mx].size(); j++)
        if(list_hash[mx][j]==x)
            return;
    list_hash[mx].push_back(x);
}

inline int check1(int x){
    return origin[x];
}

inline int check2(int x){
    return origin_plus[x%MD][x];
}

inline int check3(int x){
    return origin_hash[x%MD];
}
分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *