stl测试

以下测试都在学校电脑进行我觉得应该比考试机器慢一点。。

1.map

map的速度测出来和放入数值大小有很大关系

比如

#include <bits/stdc++.h>

using namespace std;

#define rep(i,h,t) for (int i=h;i<=t;i++)

const int N=1e6;

const int mo=;

map<int,int> M;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  rep(i,,N)

  {

    int x=rand()%mo;

    M[x]++;

  }

  int ans=;

  rep(i,,N)

  {

    int x=rand()%mo+,y=rand()%mo+;

    ans+=M[x]-M[y];

  }

  cout<<ans<<endl;

  return ;

}

在mo=100的时候开O2仅0.4s 不开O2 1.2s

而在mo=1e9的情况下开O2跑了7s 不开O2跑了12s

于是我尝试了一下hash 开不开O2都差不多0.7s

#include <bits/stdc++.h>

using namespace std;

#define rep(i,h,t) for (int i=h;i<=t;i++)

const int N=1e6;

const int mo=;

map<int,int> M;

const int hashmo=1e7+;

struct re{

  int a,b;

}ha[hashmo+];

struct hash{

  void insert(int x)

  {

    int y=x%hashmo;

    while (ha[y].a&&ha[y].a!=x) y++;

    ha[y].a=x; ha[y].b++;

  }

  int find(int x)

  {

    int y=x%hashmo;

    while (ha[y].a&&ha[y].a!=x) y++;

    return ha[y].b;

  }

}H;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  rep(i,,N)

  {

    int x=rand()%mo;

    H.insert(x);

  }

  int ans=;

  rep(i,,N)

  {

    int x=rand()%mo+,y=rand()%mo+;

    ans+=H.find(x)-H.find(y);

  }

  cout<<ans<<endl;

  return ;

}

gprof了一下

% cumulative self self total
time seconds seconds calls ns/call ns/call name

50.00 0.27 0.27 2000000 135.00 135.00 hash::find(int)
42.59 0.50 0.23 1000000 230.00 230.00 hash::insert(int)

所以不到没有时间或者题目时间对这个很宽松的时候（或者这个比较难写hash）

尽量使用手写hash

hash在5e6的时候

不开O2 3.7s 开O2 3.7s

所以考试的上限大概就这么多了

当然hash在模数较小的情况下表现也会更好

2.set

首先set的操作比较多，先说一下

insert嘛人人都知道

find注意只能查找这个元素，如果没有就会指向end（空）

lower_bound 查找.>=x的最小元素 upper_bound 查找>x的最小元素

erase(x) 删去所有等于x的元素注意如果你用multiset然后想只删一个那么可以it=S.find() S.earse(it)

count(x) 查找=x的元素个数（这个操作并没有啥用因为可以用map）

但是有的时候我们需要重载运算符

如下

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

struct cmp{

  bool operator () (int x,int y)

  {

    return x>y;

  }

};

set<int,cmp> S;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  return ;

}

这样就定义了从大到小的set

但这种情况下假如要用lower_bound怎么办呢

我们测试一下

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

struct cmp{

  bool operator () (int x,int y)

  {

    return x>y;

  }

};

set<int,cmp> S;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  S.insert(); S.insert(); S.insert(); S.insert();

  cout<<*S.upper_bound()<<" "<<*S.lower_bound()<<endl;

  return ;

}

输出的是3,4

其实我们可以这么去看，现在元素是从大到小排序

我们upper_bound 是查找这个数右边（不包括自己）而lower_bound是查找这个数右边包括自己的

于是这样我们就可以在cmp后继续使用lower/upper _bound查找了

但是现在还有一个问题，如果我想查找<=x的最大数呢

方案1：修改cmp

方案2：S.upper_bound()-- (当然要特判断一下不存在）

如果查找<x的最大数呢

方案2：S.lower_bound()--（同理也得特判）

另一个问题是set的遍历

有的时候我们写启发式合并然后时间比较宽松就会用set来替代

（平衡树毕竟个人感觉是最难调的数据结构）

for (it=S.begin();it!=S.end();it++) 这样遍历

有的时候我们需要求it的后继但并不像改变it的值,可以这么写

#define setit set<int>::iterator

setit scc(setit it )

{

setit it2=it; it2++; return it2;

}

这就是it的基本操作了

接下来开始测速度

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define ll long long

struct cmp{

  IL bool operator () (int x,int y)

  {

    return x>y;

  }

};

set<int,cmp> S;

set<int,cmp>::iterator it;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  int n=1e6;

  rep(i,,n) S.insert(rand());

  ll ans=;

  for (it=S.begin();it!=S.end();it++)

  {

    ans+=*it;

  }

  cout<<ans<<endl;

  return ;

}

不开O2 3s 开O2 2s

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define ll long long

struct cmp{

  IL bool operator () (int x,int y)

  {

    return x>y;

  }

};

set<int,cmp> S;

set<int,cmp>::iterator it;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  int n=1e6;

  rep(i,,n) S.insert(rand()%);

  ll ans=;

  for (it=S.begin();it!=S.end();it++)

  {

    ans+=*it;

  }

  cout<<ans<<endl;

  return ;

}

不开O2 0.5s 开O2 0.3s

这个代码和刚才一样

当数值都较小时就快很多

我不是很清楚原理

不过这也告诉了我们离散化在卡常上挺重要的

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define ll long long

struct cmp{

  IL bool operator () (int x,int y)

  {

    return x>y;

  }

};

set<int,cmp> S;

set<int,cmp>::iterator it;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  int n=1e6;

  rep(i,,n) S.insert(rand());

  ll ans=;

  rep(i,,n) ans+=*S.find(rand());

  cout<<ans<<endl;

  return ;

}

不开O2 4.6s 开O2 3.6s

同理把find变成upper_bound时间几乎差不多

所以考试的时候当数据范围不是很大的时候 1e6次插入基本可以接受

3.vector

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define ll long long

vector<int> ve;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  int n=1e7;

  rep(i,,n) ve.push_back(rand());

  ll ans=;

  rep(i,,n) ans+=ve[i-];

  cout<<ans<<endl;

  return ;

}

不开O2 0.85s 开O2 0.75s

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define ll long long

const int N=2e7;

int ve[N];

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  int n=1e7;

  rep(i,,n) ve[i]=rand();

  ll ans=;

  rep(i,,n) ans+=ve[i-];

  cout<<ans<<endl;

  return ;

}

而数组不开O2 0.55s 开O2 0.4s

这说明了的确会慢一点

再大的数组一般用不到大的数组访问还是挺慢的

4.queue

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define ll long long

queue<int> q;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  int n=1e7;

  rep(i,,n) q.push(rand());

  ll ans=;

  rep(i,,n) ans+=q.front();

  cout<<ans<<endl;

  return ;

}

不开O2 2s 的确是非常的慢

不过开O2 0.6s？？？？这个还可以

所以在一些线性算法时间比较仅的情况下尽量使用数组

5.deque

这个东西让我很震惊

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define ll long long

deque<int> q;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  int n=1e7;

  rep(i,,n) q.push_front(rand());

  ll ans=;

  rep(i,,n) ans+=q.front();

  cout<<ans<<endl;

  return ;

}

不开O2 1s 开O2 0.5s

比queue快是什么操作啊。。

这个东西简直是个神仙东西。。

还有各种操作。。（在雅礼里面写了下次再补）

6.priority_queue

这个东西强O2需要求啊。。

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define ll long long

priority_queue<int> q;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  int n=1e6;

  rep(i,,n) q.push(rand());

  ll ans=;

  rep(i,,n) ans+=q.top(),q.pop();

  return ;

}

不开O2 3s 开O2 0.6s

也就是说不开O2下和set速度差不多开O2吊打set

像去年d1t3 最坏情况下5e6次priority操作所以开始写就要意识常数问题了

最短路一般没什么优化余地我去网上看了一下线段树和堆优化

几乎跑的差不多

巴特西

stl测试

最新文章

热门文章