gp_hash_table 的故事

konyakest · 2024-02-10 22:18:29 · 个人记录

今天，看到题单上面的 90pts 不顺眼，就想着继续卡常

然后，测了一下数据点8：

我以为的瓶颈：0.006597s

gp_hash_table 插入数据：0.906644s

（我本机速度较快，实际上达不到这个时间）

然后，我直接把 gp_hash_table 换成了 cc_hash_table，您猜怎么着，过了！

然后，我才发现，原来是出题人故意卡 gp_hash_table

以下是实验过程：

• 自定义 hash 三次测试的结果：

const int maxn=2e5+5;

int t,n,m,l,r,a[maxn];

void solve(){
    mt19937 gen(random_device{}());
#if 0
    auto hsh=[](int x)->size_t{return hash<bitset<32>>()(x);};
    static gp_hash_table<int,int,decltype(hsh)> mp(hsh);
#else
    static gp_hash_table<int,int> mp;
#endif
    mp.clear();
    F(i,1,2e5) mp[gen()]++;
}

signed main(){
    F(i,1,100) solve();
    return not "FST";
}

自定义 hash：

>>> (0.926+0.973+0.938)/3
0.9456666666666665

非自定义 hash：

>>> (0.732+0.725+0.719)/3
0.7253333333333333

后者仅慢 30.4\%

cc_hash_table：1.921，1.744

• 然后就是特殊构造的数据（指这个测试点，仅保留向 gp_hash_table 中插入数据的部分代码）：（考虑到 IO 带来的时间，以下计时使用 user）

自定义 hash：

>>> (0.118+0.133+0.121)/3
0.124

非自定义 hash：

>>> (0.877+0.856+0.893)/3
0.8753333333333334

cc_hash_table：0.138,0.176（你没有看错，cc_hash_table 前者更快）

所以，我的建议是使用 gp_hash_table 加上自定义的 hash 函数

当然，用 cc_hash_table 也是不错的选择，只不过就要承受数据随机是的 2 倍常数

另外，(gp/cc)_hash_table 的遍历的时间相较于插入是可以忽略不计的

double ans1,ans2;

void solve(){
    mt19937 gen(random_device{}());
#if 1
    auto hsh=[](int x)->size_t{return hash<bitset<32>>()(x);};
    static gp_hash_table<int,int,decltype(hsh)> mp(hsh);
#else
    static gp_hash_table<int,int> mp;
#endif
    mp.clear();
    int st=clock();
    F(i,1,2e5) mp[gen()]++;
    ans1+=(clock()-st)*1.0/CLOCKS_PER_SEC;
    st=clock();
    volatile unsigned res=0;
    for(auto i:mp) res+=i.x+i.y;
    ans2+=(clock()-st)*1.0/CLOCKS_PER_SEC;
}

signed main(){
    F(i,1,100) solve();
    cout<<ans1<<" "<<ans2<<endl;
    return not "FST";
}

输出：

0.783067 0.162547

然后，交上去就打脸了，实测 cc_hash_table 比 gp_hash_table 快

彩蛋：你的代码看似没有使用多态，但是 gp_hash_table 的虚表的汇编有 170 行，不愧是你，pbds