怎样更快？
在程序设计中，往往会寻求代码的运行速度。
当你面对 TLE 的残酷现实却不愿承认自己的算法有问题时，卡常是一个很好的办法。
卡常数、又称底层常数优化，特指在 OI/ACM-ICPC 等算法竞赛中针对程序基本操作进行的底层优化，一般在对程序性能要求较为严苛的题目或是在算法已经达到理论最优时间复杂度时使用，有时也用于非正解的强行优化。实现方法有使用 register 寄存器关键字、利用空间连续性使数组进入缓存、输入输出优化等。
1. 快读 & 快写
总所周知，字符输入输出比标准输入输出快的很。
快读和快写就是运用了这个原理。
快写模板（循环）：
template <typename T> | |
void read (T &x) { | |
x = 0; | |
int f = 1; | |
char ch = getchar (); | |
while (!isdigit (ch)) { //isdigit 在 < cctype > 中 | |
if (ch == '-') { | |
f = -1; | |
} | |
ch = getchar (); | |
} | |
while (isdigit (ch)) { | |
x = x * 10 + (ch - 48); | |
ch = getchar (); | |
} | |
x *= f; | |
return; | |
} |
用法： read (x); // 输入并赋值
快写（递归）：
template <typename T> | |
void write(T x) { | |
if(x < 0) { | |
putchar('-'); | |
x = -x; | |
} | |
if(x > 9) { | |
write(x / 10); | |
} | |
putchar(x % 10 + '0'); | |
return; | |
} |
用法： write (x); // 输出
2. 位运算
能用位运算就用。
在乘除运算上，最好用左移和右移代替。
2 * 2 可写成 2 <<1, 2 * 10 可写成 (2 << 1) + (2 << 3)。
90 / 2 可写成 90 >> 1, 128 / 16 可写成 128 >> 4。
小知识：
| 位运算符号 | 位运算关键字版符号 |
|---|---|
| & | bitand |
| ` | ` |
| ~ | compl |
| ^ | xor |
| &= | and_eq |
| ` | =` |
| ^= | xor_eq |
位运算的其他应用：
1）代替模运算
17 % 2 可写成 17 & 1，45 % 4 可写成 45 & 3, 986 % 16 可写成 986 & 15。
2）快速幂
快速幂模板：
int qk_pow (int x, int n){ | |
if (n == 0) { | |
return 1; | |
} | |
int t = 1; | |
while (n) { | |
if (n & 1) { // 用 & 代替 % | |
t *= x; | |
} | |
n >>= 1; // 用 >> 代替 * | |
x *= x; | |
} | |
return t; | |
} |
3）Swap 函数
void Swap(int &a, int &b){ | |
a ^= b ^= a ^= b; | |
return; | |
} |
这个代码很妙，可以细细品味。
3.inline
在声明函数之前写上 inline ，可以加快一下函数调用，但只能用于一些操作简单、调用频繁的函数。涉及递归，大号的循环等很复杂的函数，编译器会自动忽略 inline 。
如快读函数可写成：
template <typename T> | |
inline void read(T &x) { | |
x = 0; | |
int f = 1; | |
char ch = getchar(); | |
while(!isdigit(ch)) { | |
if (ch == '-') { | |
f = -1; | |
} | |
ch = getchar(); | |
} | |
while(isdigit(ch)) { | |
x = x * 10 + (ch - 48); | |
ch = getchar(); | |
} | |
x *= f; | |
return; | |
} |
但有时 inline 会被忽略。
4. 寄存器
假如你要拿个钥匙，一个在你裤兜里，一个在你车上，你拿哪一个？
就近原则。
从距离上来说，内存条相较于寄存器来说离 C P U \tt CPU CPU 更远。
在时间相等的情况下，时间与路程成正比。
从工作原理上来说，寄存器的工作原理比内存简单的多。
综上，寄存器与内存之间具有差异，但差异不大。因此利用寄存器来提高访问速度往往运用与经常被访问的变量。
例如：
for(register int i = 1; i <= 1000000000; i ++) |
register 关键字表示将变量 i 存于寄存器中。代码中变量 i 将被访问 1000000000 次，每一次访问都节省若干时间，乘上 1000000000 便不可忽略。在这个代码中优化后会快 1.5sec→1.7sec 。
5. 三目运算符
相较于 i f e l s e \tt if \ else if else 语句，三目运算符的汇编指令更短。
在少量的运行中，二者的区别微乎其微。
但运行次数庞大时， 三目运算符的优势便显现出来。
如 min 函数
int min(int a, int b) { | |
return a > b ? a : b; | |
} |
问号前是判断条件，如为真则执行冒号前的语句，否则执行冒号后的语句。
6. 常数的声明
尽量将常数声明成常量。
如：
const int mod = 100000007; 比 int mod = 100000007; 要快。
7.#pragma 指令
经常提到 O2 这一说法，它的实现为： #pragma GCC optimize (2)
当然还有 O1、O3、Os。
#pragma GCC optimize (1) | |
#pragma GCC optimize (2) | |
#pragma GCC optimize (3,"Ofast","inline") | |
#pragma GCC optimize (s) | |
还有一堆： | |
#pragma GCC optimize (3) | |
#pragma GCC optimize ("Ofast") | |
#pragma GCC optimize ("inline") | |
#pragma GCC optimize ("-fgcse") | |
#pragma GCC optimize ("-fgcse-lm") | |
#pragma GCC optimize ("-fipa-sra") | |
#pragma GCC optimize ("-ftree-pre") | |
#pragma GCC optimize ("-ftree-vrp") | |
#pragma GCC optimize ("-fpeephole2") | |
#pragma GCC optimize ("-ffast-math") | |
#pragma GCC optimize ("-fsched-spec") | |
#pragma GCC optimize ("unroll-loops") | |
#pragma GCC optimize ("-falign-jumps") | |
#pragma GCC optimize ("-falign-loops") | |
#pragma GCC optimize ("-falign-labels") | |
#pragma GCC optimize ("-fdevirtualize") | |
#pragma GCC optimize ("-fcaller-saves") | |
#pragma GCC optimize ("-fcrossjumping") | |
#pragma GCC optimize ("-fthread-jumps") | |
#pragma GCC optimize ("-funroll-loops") | |
#pragma GCC optimize ("-fwhole-program") | |
#pragma GCC optimize ("-freorder-blocks") | |
#pragma GCC optimize ("-fschedule-insns") | |
#pragma GCC optimize ("inline-functions") | |
#pragma GCC optimize ("-ftree-tail-merge") | |
#pragma GCC optimize ("-fschedule-insns2") | |
#pragma GCC optimize ("-fstrict-aliasing") | |
#pragma GCC optimize ("-fstrict-overflow") | |
#pragma GCC optimize ("-falign-functions") | |
#pragma GCC optimize ("-fcse-skip-blocks") | |
#pragma GCC optimize ("-fcse-follow-jumps") | |
#pragma GCC optimize ("-fsched-interblock") | |
#pragma GCC optimize ("-fpartial-inlining") | |
#pragma GCC optimize ("no-stack-protector") | |
#pragma GCC optimize ("-freorder-functions") | |
#pragma GCC optimize ("-findirect-inlining") | |
#pragma GCC optimize ("-fhoist-adjacent-loads") | |
#pragma GCC optimize ("-frerun-cse-after-loop") | |
#pragma GCC optimize ("inline-small-functions") | |
#pragma GCC optimize ("-finline-small-functions") | |
#pragma GCC optimize ("-ftree-switch-conversion") | |
#pragma GCC optimize ("-foptimize-sibling-calls") | |
#pragma GCC optimize ("-fexpensive-optimizations") | |
#pragma GCC optimize ("-funsafe-loop-optimizations") | |
#pragma GCC optimize ("inline-functions-called-once") | |
#pragma GCC optimize ("-fdelete-null-pointer-checks") |
重点：开个 O2 就行了，欲速则不达。（指令集开多了会有负面作用）
8. 一些奇奇怪怪的卡常小知识
后置 ++ 需要保存临时变量以返回之前的值，在 STL 中非常慢。事实上，int 的后置 ++ 在实测中也比前置 ++ 慢 0.5 倍左右。
逗号比分号要快（神奇）。
bool 很慢，尽量开 int（疑惑）。
一些卡常在正规比赛中 禁用 。
