#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<random>
#include<time.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<unordered_map>
#define ll long long
using namespace std;
using namespace __gnu_pbds;
const int MAXN=1e5+10;
int pos[MAXN],cnt;mt19937 R;
struct node{int x,y,w;};vector <node> e;
inline bool cmp(node x,node y)
{return x.w<y.w;}
"ValueType" <ll,int> H;
inline ll F(int x,int y)
{return ((1ll*x)<<32)|y;}
signed main()
{
int n=100000,m=100000,q=250;
for(int i=1;i<=n;++i) pos[i]=i;
for(int i=1,x,y,w;i<=m;++i)//插入 m 个数
{
w=R()%123456789+1;
x=R()%n+1,y=R()%n+1;
if(x>y) swap(x,y);ll pos=F(x,y);
if(!H[pos]) H[pos]=w;
else H[pos]=min(H[pos],w);
}
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
for(auto now:H)//遍历一遍
{
ll pos=now.first;int w=now.second;
int x=pos>>32,y=pos^((1ll*x)<<32);
e.push_back({x,y,w});
}
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
// sort(e.begin(),e.end(),cmp);
for(int i=0;i<e.size();++i)//修改为编号
H[F(e[i].x,e[i].y)]=i;
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
for(int o=1,k=400;o<=q;++o)//查询一些东西
{
shuffle(pos+1,pos+1+n,R);
for(int i=0;i<k;++i) for(int j=i+1;j<k;++j)
{
int x=pos[i],y=pos[j];
if(x>y) swap(x,y);ll POS=F(x,y);
if(H.find(POS)!=H.end()) ++cnt;
}
}
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';return 0;
}
你写出了这样的代码,大概是想找出 \(q=250\) 个点集大小为 \(k=400\) 的导出子图。
其中你需要实现一个 pair
对 int
的映射,于是你将 pair
压成了 long long
。
尽管不一定很卡常,但是你精益求精的使 "ValueType" = gp_hash_table
,打开了 O2
。
然后你发现输出是:
0.727675
0.729566
1.07756
甚至查询都跑不出来。
你不以为意,大概只是正好这样的数据能卡掉 gp_hash_table
,但是没关系,因为你还有 cc_hash_table
可以替换。
你幸高采烈的将 cc_hash_table
替换上,你发现输出是:
0.008778
0.01072
0.011504
0.350058
不错,很快,你提交后吃了一发罚时,它说你 TLE 了。
你更加疑惑了,但是你认为可能常数藏在一些看不见的地方,于是开始卡常。
但是当然你想到用 unordered_map
来试一试,你发现输出是:
0.010581
0.012657
0.013935
0.600974
明显比 cc_hash_table
慢啊,于是你继续卡常。
但是两个多小时后你卡不动了,你突然想到了什么,对 cc_hash_table
打开了 ubsan
:
0.023092
0.02854
0.031228
/usr/include/c++/9/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp:530:15: runtime error: member access within null pointer of type 'struct entry'
0.915729
所以或许是 cc_hash_table
有 bug?我不知道啊。
但是对于 gp_hash_table
:
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<unordered_map>
#define ll long long
using namespace std;
using namespace __gnu_pbds;
gp_hash_table <ll,int> H;
signed main()
{
int n=500000,cnt=0;
for(int i=1,x,y;i<=n;++i)
{
x=rand()%n+1,y=rand()%n+1;
// if(x>y) swap(x,y);
H[(1ll*x)<<32|y]=i;
}
}
这个跑 \(0.15s\),而把注释删了跑 \(9.9s\)。大概是因为过于不均匀?
标签:hash,int,pos,cc,哈希,table,include From: https://www.cnblogs.com/int-R/p/18518522/hash