前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >总结ACM竞赛中常见的影响运行速度的几点

总结ACM竞赛中常见的影响运行速度的几点

作者头像
ACM算法日常
发布2022-03-04 12:44:25
1.5K0
发布2022-03-04 12:44:25
举报
文章被收录于专栏:ACM算法日常

转载声明:本文转自知乎,已经过作者同意转载。

前一场的codeforces的D题有很多人反应思路差不多但是会TLE,基本上都是卡输入输出了,所以这里就在这里总结一下,有哪些会影响程序的运行速度。不过这是建立在你的时间复杂度是正确的情况下。

cin/cout 解绑

这是一个初学者基本上都会遇到的坑,原生的cin/cout的速度非常慢,因为要和scanf/printf进行同步。

所以需要加上。

代码语言:javascript
复制
std::ios::sync_with_stdio(false);std::cin.tie(0);

注意解绑后,不能使用scanf和printf了,快读也是不可以的,因为快读的getchar也是C语言里面的。

解绑后的cin/cout的速度是比scanf要快的,cin输入的数据类型是在编译时期就会确定的,而scanf则是在运行时解析字符串。也就是你可以写出这样的代码。

代码语言:javascript
复制
int main() {
 char s[20];
 cin >> s;
 int n;
 scanf(s, &n);
 cout << n << endl;
}

endl

endl在使用的时候不仅仅是换行,还会清空缓冲区。速度上可能比"\n"换行慢了10倍。

所以大家完全可以加上

代码语言:javascript
复制
#define endl "\n"

O3/O2优化

如果你的代码里有stl的话,请一定加上这句话,开启O3优化。

代码语言:javascript
复制
#pragma GCC optimize(3)

不过一般的OJ都是默认开启的,洛谷需要手动点一下。只要记住一直带着O3优化就可以了。

原理的话我可以举个例子。

比如这段代码。

不开优化的汇编是这样的

而我们只需要加上O3优化

汇编就变成了这样

编译器在编译的时候就帮你算出了一些值。

可以简单的理解为,开了优化,编译器就会延长编译的时间来进行优化,使得程序的运行时间尽可能的短。

不过比赛的时候基本上都会开上优化的。还有一些特殊的情况,据说由于开了O3后生成的汇编指令太多导致速度变慢,但是我没有遇到过。大部分的比赛都是开的O2优化。

vector的push_back()

vector的push_back()虽然是均摊的O(1),但是当数据量大的时候会很慢。所以如果需要使用的话。可以

代码语言:javascript
复制
signed main() {
 cin >> n;
 vector<int>v(n + 1);
 for (int i = 1; i <= n; i++)cin >> v[i];
}

还有一个stl叫deque,可以前push/pop,后push/pop ,还有随机读取的能力。但是常数会大一点。

来源:STL容器 vector,list,deque 性能比较 - sailing - C++博客(http://www.cppblog.com/sailing/articles/161659.html)

不过这个测试好像没有开优化,所以会出现vector比数组慢很多。我本地开优化测试跑的速度为

数组0.2185s vector 0.4057s 不会出现数量级的差距。

unordered_map / set

如何你只是需要一个映射关系的话,不需要有序的话,可以尝试unordered_map。看了一些测试数据,基本上快了一倍吧。

inline/register

这个东西在开启了O3优化后基本上编译器都帮你干了。所以可以不用说了。

#define int long long

很多人觉得这个会影响速度,但其实看过一些测试数据后你会就发现int 和 long long 的速度差不多的。

C++ 基本计算的速度 | 小灰灰灰灰的博客(https://blog.lyh543.cn/2019/08/20/cpp-calculating-efficiency/)

但是浮点数就慢很多了,大概差一个数量级。

当然long long 在取模除法的时候就会明显慢于int,所以需要看情况来使用。

这个地方可能比较迷惑,所以我自己也测试了一下。

测试代码如下

代码语言:javascript
复制
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int rd() {
 return rand()*rand();
}
signed main() {
 int re = 0;
 double res = 0;
 for (int cnt = 1; cnt <= 10; cnt++) {
  clock_t start, end;
  start = clock();
  int s = 0;
  for (int i = 1; i <= 10000000; i++) {
   s += i;//累加
   s += rd();//加随机数
   s = max(s, rd());// 判断
   s = rd() / i;//除法
   s = rd() % rand();//取模
   s += (rd() % i + i + max(rd(), rd()) % 114514 + i + i + i + i / 114 + i * 514) % 114514;//混合
  }
  end = clock();
  res += (double)(end - start) / CLOCKS_PER_SEC;
  re = s ^ re;
 }
 cout << res / 10 << endl;
 return re;
}

也就是说当代码中已有简单的运算的时候,define int long long 的影响很少。

但是如果是有很多取模运算的时候,就要考虑一下了。

const int mod

不加const的话,取模会慢很多的。我当初百度之星有一道斯特林数的题就是因为没有加const导致T了好几发。

但是开了O3后,编译器会帮你手动优化的。

结构体线段树

有两种写线段树的方法,一种是数组,另一种是包结构体里面。

代码语言:javascript
复制
struct node {
 int sum, lz;
}tree[MAXN << 2];

int sum[MAXN << 2];
int lz[MAXN << 2];

理论上第一个cache命中率高一些,我用洛谷上的线段树模板题尝试过,快不了多少其实。

不过用结构体写可以用代码补全(确信

存图的方式

我测试了一下vector和链式前向星的速度。

vector跑了0.0488s ,链式前向星跑了 0.0224s ,明显是链式快一些。

云剪贴板 - 洛谷(https://www.luogu.com.cn/paste/ov0xs40u) 代码这里

数据是使用洛谷的数据生成器生成的一棵50000个节点的树,其中40%的节点呈现链状,35%的节点呈现菊花图状,剩余25%的节点随机加入。

总结,基本上就是开了优化后,加上解绑和"\n"能解决大部分的问题。

当然某些毒瘤题目除外。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-02-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • cin/cout 解绑
  • endl
  • O3/O2优化
  • vector的push_back()
  • unordered_map / set
  • inline/register
  • #define int long long
  • const int mod
  • 结构体线段树
  • 存图的方式
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档