一些卡常技巧
0 简介
首先我们要知道 卡常 到底是什么。
卡常数,又称底层常数优化,是信息学竞赛中一种针对程序基本操作进行空间或时间上优化的行为,与时间复杂度或剪枝有别。
——百度百科
虽然这段文字来源于百度百科,但是不得不承认卡常数就是这么个简单的东西((
它虽然无法优化时间复杂度,但往往可能可以使得错误的复杂度松过一些题目。同时,过大的常数也可能导致一些复杂度正确的程序发生超时。可见,养成一个小常数的代码习惯是十分重要的。
那么就从几个方面来简单讲一下如何减小自己的常数。
注:本文默认已经开启 O2 优化,故一些显然会被编译器优化掉的东西我们不去考虑,一些冷门或容易被优化掉的卡常手段会在偏文末的地方讨论。
1 寻找卡常点
在卡常之前,我们要先知道我们什么地方常数大会影响复杂度。
比如说这样一段代码:
cin >> x;
for (int i = 1;i <= n;++ i){
for (int j = 1;j <= m;++ j){
for (int k = 1;k <= q;++ k){
/* do something */
}
}
}
显然复杂度是 $O(nmq)$ 的,这个时候你去优化这个 cin >> x
就显得没什么必要。
(当然如果你想处处卡常的话另当别论)
所以我们引入 复杂度瓶颈 的概念。
这个概念没什么好说的,可以理解成 “删掉了这一段可以直接优化复杂度但是我又没办法删就很难受” 的地方。
所以我们为了在最短的优化时间内达到最大的优化效果,我们要找到常数比较大的地方,尤其是复杂度瓶颈处,对这些地方进行优化会给代码的运行效率带来不错的提升。
下面会列举出一些常见的优化效果比较明显的卡常点。
2 IO优化
在传统的 OI 比赛中,题目往往有输入和输出。
所以对这种必然存在的东西进行优化不仅能提升代码效率,还可以十分方便地在代码之间进行迁移。
一般我们最常见的输入输出方式是 scanf()
和 printf()
。
或者厉害一点,我们用更快的 getchar()
和 putchar()
写快输快读。
template <typename T>
inline void read(T &x){
x = 0;int fu = 1;
char c = getchar();
while(c > 57 || c < 48){
if(c == 45) fu = -1;
c = getcha();
}
while(c <= 57 && c >= 48){
x = x * 10 + c - 48;
c = getchar();
}
x *= fu;
}
template <typename T>
inline void fprint(T x){
if(x < 0) putchar(45), x = -x;
if(x > 9) fprint(x / 10);
putchar(x % 10 + 48);
}
但是这些东西太逊了,因为它们是 实时读入、实时输出 的。
众所周知,离线算法一般比在线算法快(什么鬼逻辑),所以一次把整个输入文件全部读进来,把整个输出文件全部输出去,就会快一些。
我们意识到,现在 OI 中大部分的传统题都只有一个输入文件和一个输出文件,所以全部读进来和全部输出去 完 全 可 行 。你大可以理解成我们把输入全部离线下来(((
c++ 里面有两个函数 fread()
和 fwrite()
,它们的作用就是以很高的速度一次读入或输出一大堆东西。
但是这样子,我们怎么用它来 模拟实时输入输出 呢?
其实很简单,把我们刚才的快读快输改一下,不难发现我们在这两个函数里最主要用到的是 getchar() putchar()
两个函数,我们把这两个函数模拟出来就行了。
我们的方式是把所有读入全部压缩到一个内存池里面(应该不会有出题人空间开的比输入量还小吧),然后用 指针的移动 模拟 getchar()
的过程,这样就可以模拟 一个一个字符的读入,与 getchar()
完全一致, putchar()
同理。
具体下来就是这么写:
const int DPAIRSIZ = 1 << 18;//定义内存池大小
char BB[DPAIRSIZ], *SS = BB, *TT = BB;//开内存池
inline char getcha(){return SS == TT && (TT = (SS = BB) + fread(BB, 1, DPAIRSIZ, stdin), SS == TT) ? EOF : *SS ++;}
template <typename T>
inline void read(T &x){//照常写就行了
x = 0;int fu = 1;
char c = getcha();
while(c > 57 || c < 48){
if(c == 45) fu = -1;
c = getcha();
}
while(c <= 57 && c >= 48){
x = x * 10 + c - 48;
c = getcha();
}
x *= fu;
}
char out[DPAIRSIZ], *Out = out;
#define flush() fwrite(out, 1, Out - out, stdout)
inline void putcha(char x) {*Out++ = x;if(Out - out >= (DPAIRSIZ)) flush(), Out = out;}//同理
template <typename T>
inline void fprint(T x){
if(x < 0) putcha(45), x = -x;
if(x > 9) fprint(x / 10);
putcha(x % 10 + 48);
}
这样会快很多。
你可能觉得这样已经没得优化了。
但是我们不满足于此。
我们意识到有一些题目中满足形如 “本题中所有数为非负整数” 的条件。
此时,我们意识到我们的快读里面有判断负数的环节。
删掉就行了,跑得更快了,而且效率提升比较显著。
const int DPAIRSIZ = 1 << 18;//定义内存池大小
char BB[DPAIRSIZ], *SS = BB, *TT = BB;//开内存池
inline char getcha(){return SS == TT && (TT = (SS = BB) + fread(BB, 1, DPAIRSIZ, stdin), SS == TT) ? EOF : *SS ++;}
template <typename T>
inline void read(T &x){//照常写就行了
x = 0;char c = getcha();
while(c > 57 || c < 48) c = getcha();
while(c <= 57 && c >= 48){
x = x * 10 + c - 48;
c = getcha();
}
}
char out[DPAIRSIZ], *Out = out;
#define flush() fwrite(out, 1, Out - out, stdout)
inline void putcha(char x) {*Out++ = x;if(Out - out >= (DPAIRSIZ)) flush(), Out = out;}//同理
template <typename T>
inline void fprint(T x){
if(x > 9) fprint(x / 10);
putcha(x % 10 + 48);
}
而且这个方法可以拿过来读字符串什么的,具体方法请自行研究。
3 指针与动态内存
指针是个好东西,据说在一般的情况下就十分优秀,但是这里我们考虑其用于 动态初始长度数组 。
用指针比用什么 std::vector
处理 动态初始长度数组 好到不知道哪里去了,不信的话你看看这个。
指针是什么东西应该是个人都知道,我就不赘述了。
我们具体看看指针是怎么实现动态初始长度数组的。
一种很 naive 的方法是 int *p = int new[N];
,就是申请 $N$ 这么多空间。
不难发现这样还是不断 动态 申请新内存,还是不够优秀。
所以我们直接算好内存,在一开始就把所有内存开好。
比如我们算下来,所有数组长度之和为 $N$ 。
那么我们直接这么写:(这东西是在学 压位 Trie 的时候看 skip2004 的代码学到的)
int buff[N + 5], *ed = buf + sizeof(buff) / sizeof(int);
inline int *alloc(int siz){return ed -= siz;}
这样子相当于一开始就开好了一个大小为 $N$ 的大内存池,那么我们进行后续的内存分配就只需要确定 起点 了,就会快一些。
具体来说,这么写:
int *p = alloc(size);//比如说我要开 size 的空间
就很方便快捷。
而且对于那些后面数据 允许并且一定 会覆盖前面数据的问题,用这种方法可以通过直接重置 ed
指针来节省空间,十分方便。
程序的其他地方使用指针其实也可以使程序变快,甚至有时会更好写。
所以学指针是好的。
4 常量
有些时候,我们程序里面的一些变量在定义之后就不会被更改,比如说 模数、块长 什么的。
我们用常量来定义它们也可以达到优化常数的效果(而且据说这个东西编译器没法帮你优化)。
而且开常量有一个好处:要是我们什么地方手残,一个不小心把常量给改了,编译器还会直接报错帮你搞定。
而且这东西比什么宏高到不知道哪里去了
一些常见的开常量的地方如下:
const int MOD = 998244353;//模数
const int block = 114514;//块长(当然大概率不会有这么长的块长)
const double alpha = 0.75;//替罪羊树(或其他东西)的阈值
其他东西开成常量可能反而会变慢的说,还是别乱开,只开开常用常量比较好。
好像说对常量取模编译器有优化?
5 循环展开
“你影响它循环展开了。”
2021CCF冬眠营上面讲过一个《并行算法》,不难发现并行算法可以大大加快处理一个问题的速度。那么我们也要想办法刺激我们的计算机并行运算。而这个方式就是 循环展开。
比如这样一段代码:
unsigned int s = 0;
for (int i = 1;i <= n;++ i)
s += a[i];
return s;
我们把它循环展开,就是这么写:
unsigned int s[4] = {0, 0, 0, 0};//如果写一起会引起竞争,我们都知道,竞争是不好的
switch(n & 3){
case 3: s[0] += a[n - 2];
case 2: s[0] += a[n - 1];
case 1: s[0] += a[n];
}
n -= 3;
for (int i = 1;i <= n;i += 4){
s[0] += a[i];
s[1] += a[i + 1];
s[2] += a[i + 2];
s[3] += a[i + 3];
}
return s[0] + s[1] + s[2] + s[3];
乍看之下这样写没什么区别,甚至可能更慢,但是,其实这样好像说会刺激 CPU 并发运算,从而提高运行效率。
而且编译器有些时候没办法优化到这种程度,手动循环展开应该会比编译器高明一些。
我们再看两份代码:
int a[N + 5];
for (int i = 1;i <= N;++ i) read(a[i]);
unsigned int s = 0;
for (int i = 1;i <= N;++ i) s += a[i];
和
int a[N + 5];
for (int i = 1;i <= N;++ i){
int x;read(x);
s += x;
}
乍看之下第二份代码还少循环一次,应该会更快。
但事实上第一份代码反而可能会更快。
因为你影响第二份代码循环展开了。
所以编译器只能优化第一份代码,更小的常数导致了第一份代码更快。
这也启示我们要尊重编译器
6 缓存命中率
有些题目里,我们发现空间变小的同时运行效率也有提升,这是为什么呢?
这就涉及到缓存命中率了。
可以简单理解成我们访问的地址是否连续,感性理解一下就知道越连续的地址我们跑得越快(因为现实中就是这样)(双重含义)。
比如这样一份代码:
const int MAXN = 100005;
int n;
LL a[MAXN], dp[MAXN];
int main(){
read(n);memset(dp, 128, sizeof(dp));
for (int i = 1;i <= n;++ i) read(a[i]);
LL ans = 0;dp[0] = 0;
for (int i = 1;i <= n;++ i){
for (int j = i;j >= 1;-- j){
chmax(dp[j], dp[j - 1] + a[i] * j);
}
}
for (int i = 1;i <= n;++ i) chmax(ans, dp[i]);
print(ans);
}
它看上去就是一副 $O(n^2)$ 的暴力的样子。
但是我们留意到我们每一次都是访问 dp[j], dp[j - 1]
这样连续的变量,所以缓存命中率高得不得了,导致它最后甚至能跑 $10^5$ 的数据。
还有一个广为人知的东西就是矩阵乘法里面:
for (int i = 0;i < n;++ i)
for (int k = 0;k < n;++ k)
for (int j = 0;j < n;++ j)
c[i][j] = a[i][k] * b[k][j];
比
for (int i = 0;i < n;++ i)
for (int j = 0;j < n;++ j)
for (int k = 0;k < n;++ k)
c[i][j] = a[i][k] * b[k][j];
要快到不知道哪里去了。
也是同一个道理。
这也解释了为什么有些时候优化了空间也会优化时间:因为提高了缓存命中率。
7 位运算
这部分编译器会帮你优化掉所以在开了 O2 的情况下没什么必要,不过对于不开 O2 的比赛来说用位运算会快不少。
位运算,就是 >>
,<<
,和 | & ^ ~
这些东西。
它们的作用就是把一个东西转成二进制之后进行运算然后再转回来,比如 1 << 1
,假设我们这里左边那个 1
是 int
类型,那么它就会像这样:
00000000 00000000 00000000 00000001
然后左移一位:
00000000 00000000 00000000 00000010
就变成了 2 。
所以左移一般用来乘上一个二的次幂,同理,右移一般用来除以一个二的次幂,而且是整除,所以一般我们会用在这种地方:
const int mid = l + r >> 1;
而且位运算全部都是 $O(1)$ 的,所以在状压的时候也十分常用。
而且位运算很快。
比如对一个形如 $2^k-1$ 的数取模时,就可以直接用 & 来优化常数,原因读者自证不难。
然后 !=
其实有时可以写成 ^
。
对于一个偶数加一可以直接用 | 1
。
但是这东西优先级对初学者比较不友好,不要乱用。
8 杂项
inline
:开了 O2 的话编译器应该会帮你优化掉,把这个加在一些 非递归 的函数前面可以一定程度上提升运行效率。i ++ 与 ++ i
:据说是++ i
快一些,但显然编译器会帮你优化掉- 取模优化:你只需要知道
%
运算挺慢的,具体怎么优化自行理解,常用的方式是重载带模数加法什么的。 - 压缩空间:能不用
long long
的 大数组 最好用int
,能不用int
的 大数组 最好用short
,甚至可以考虑压缩信息,最典型就是压位(这可能甚至可以优化复杂度),但是自己乱用然后溢出了我不负责。 - 手写数据结构:有些东西手写 可能 会比 STL 快一些,但是除非你想手写红黑树,否则用
std::set
什么的还是不错的。 - 递归改迭代?:不一定会变快,因为编译器会帮你优化掉。