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

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

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

cin/cout 解绑

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

所以需要加上。

std::ios::sync_with_stdio(false);std::cin.tie(0);

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

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

int main() {
 char s[20];
 cin >> s;
 int n;
 scanf(s, &n);
 cout << n << endl;
}

endl

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

所以大家完全可以加上

#define endl "\n"

O3/O2优化

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

#pragma GCC optimize(3)

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

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

比如这段代码。

不开优化的汇编是这样的

而我们只需要加上O3优化

汇编就变成了这样

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

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

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

vector的push_back()

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

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，所以需要看情况来使用。

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

测试代码如下

#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后，编译器会帮你手动优化的。

结构体线段树

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

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"能解决大部分的问题。

当然某些毒瘤题目除外。