0898-08980898
个/性/化/教/育/行/业/领/跑/者
2024/03/12
在竞赛中，优秀的常数有时能得到超出预期的分数。时常见过暴力卡常 AC 或高分，或某些程序复杂度正确但因常数不优而不能 AC。自己答一发（持续更新）
1. register
传说中的寄存器变量，“建议”编译器把变量放在寄存器中。只能用于栈变量，比如函数的传参。
效果：
for(int i=-1e9;++i;);
for(register int i=-1e9;++i;);
自己试试就知道
2. IO 优化（所有系统通用的）
fread(input,1,1<<30,stdin); 把整个输入文件读入
fwrite(output,1,strlen(output),stdout); 是个快速的不换行 puts，把所有输出存在里面最后输出一次
3. 取模优化（仅O2）
设模数为 mod
int inc(int x,int v){x+=v;return x>=mod?x-mod:x;}代替取模 +
int dec(int x,int v){x-=v;return x<0?x+mod:x;}代替取模 -
这两个函数在 O2 下会自动 inline，速度比你手动 inline 还要快，在 FNT 中非常好用
4. 前置 ++
后置 ++ 需要保存临时变量以返回之前的值，在 STL 中非常慢。事实上，int 的后置 ++ 在实测中也比前置 ++ 慢 0.5 倍左右（UOJ 上自定义测试）
5. 数据结构用指针代替数组
数组在用方括号时做了一次加法才能取地址！
所以在那些计算量超大的数据结构中，你每次都多做了一次加法！！！在 64 位系统下是 long long 相加，效率可想而知。
因此用指针！
这里有个 trick：
由于 C++ 中 a[b]=*(a+b)=*(b+a)=b[a]，
因此你可以用 i[a]代替 a[i]，用 1[b]代替 b[1]，多维数组同样可以，你甚至可以用 5[4[3[2[1[a]]]]]代替 a[1][2][3][4][5]。
用处，混乱代码 233。
本回答持续更新。
让常数优化成为一种习惯！
1.高效的fread fwrite这个在bzoj上面可以艹一堆rank1
2.奇怪的数据结构比如FGT这样的奇怪平衡树，它们某些操作效率相当高效
3.结构体访问很快
4.带有特技的暴力，比如OldDriverTree之类的东西
5.XJB乱剪枝什么的，挺有用的
6.循环展开，寻址优化
7.<del> #define O3 __attribute__( ( optimize( "-O3" ) ) ) <del>
8.在程序里面放上大爷（或者可爱的妹子）的名字，比如：
//Orz 花爸爸
//Yuno kawaii~
//花爸爸 Au
2017.2.09 update:
卡麻痹的常数
有毛病吧
UPD: 有空研究的人可以看这个，比如把你的FFT换成这上面的实现。
树剖求lca很快；减少寻址次数很有用，比如要访问x[i],y[i],z[i]，会有3次指针运算，打包成一个结构体a[i].x,a[i].y,a[i].z只需要1次，会快很多。
要指出的是register在O2的情况没有用，没有O2的话一些编译器会有巨大差异==
神奇的循环展开……1级缓存和3级缓存……（2017冬令营T2）
作为一个先学工程，才学 OI 并没有多久的蒟蒻，还是会卡一些常的.....
1. IO优化，fread 和 fwrite 基本已经足够，如果还想再优化，我们有 mmap....
#include <bits/stdc++.h>
#include <sys/mman.h>
#include <sys/stat.h>
#define private private:
#define public public:
class BufferedInputStream {
private char *buf, *p;
private int size;
public inline void init() {
register int fd = fileno(stdin);
struct stat sb;
fstat(fd, &sb);
size = sb.st_size;
buf = reinterpret_cast<char *>(mmap(0, size, PROT_READ, MAP_PRIVATE, fileno(stdin), 0));
p = buf;
}
public inline char nextChar() {
return (p == buf + size || *p == -1) ? -1 : *p++;
}
};
还有 isdigit 函数会快于手写判断。
2. 各种寻址优化相信大家都会，指针代替数组还是很有必要的。
3. 循环展开也许只是表面，在缓存和寄存器允许的情况下一条语句内大量的展开运算会刺激 CPU 并发(前提是你的 CPU 不是某 CPU)，如 BZOJ-3509，暴力+刺激并发就能拿下 rk1，以下是关键代码：
while (p1 <= pr) {
tmp += (*p1) * (*p2) + (*(p1 + 1)) * (*(p2 + 1)) + (*(p1 + 2)) *
(*(p2 + 2)) + (*(p1 + 3)) * (*(p2 + 3)) + (*(p1 + 4)) * (*(p2 + 4))
+ (*(p1 + 5)) * (*(p2 + 5)) + (*(p1 + 6)) * (*(p2 + 6)) + (*(p1 + 7))
* (*(p2 + 7)) + (*(p1 + 8)) * (*(p2 + 8)) + (*(p1 + 9)) * (*(p2 + 9))
+ (*(p1 + 10)) * (*(p2 + 10)) + (*(p1 + 11)) * (*(p2 + 11))
+ (*(p1 + 12)) * (*(p2 + 12)) + (*(p1 + 13)) * (*(p2 + 13))
+ (*(p1 + 14)) * (*(p2 + 14));
p1 += 15, p2 += 15;
}
4. while + switch 跳转时， switch 和 while 上出现了至少两个分支语句, 一次指令循环中要进行一次条件跳转和三次无条件跳转(开启switch跳转表优化后)，可以考虑 goto， 在使用goto语句后可以大大减少在这些控制语句上的性能消耗, 配合GCC的拓展Labels as Values使用。
5. 数据极为强大的最大流使用 vector 存图，例如 1000000 个点，4000000 条边，vector 存图只需要 450ms 左右，而前向星需要 1800ms，不信的话，你可以问问 @Menci
原因在于数据太过巨大， vector 动态的劣势已降至极低，而大量访问连续的内存地址显然比前向星更优，如下：
for (register int i = iter[v]; i < edge[v].size(); i++) {
Node *p = &edge[v][i];
if (h[v] == h[p->v] + 1) {
register int ret = sap(p->v, std::min(flow - rec, p->f), s, t, n);
p->f -= ret, edge[p->v][p->index].f += ret, iter[v] = i;
if ((rec += ret) == flow) return flow;
}
}
6. 大量调用 memcpy 还不如直接循环....
7. __attribute__，__fastcall (然而这玩意并不能在考试时用)
__attribute__((optimize("Ofast"))) __attribute__((__gnu_inline__, __always_inline__, __artificial__))
__attribute__((aligned))
8. SIMD 指令集优化矩阵乘法(同样并没有什么用)
#include <immintrin.h>
#include <intrin.h>
#define DIFFERENT_ORDER 0
static inline void lincomb_SSE(const float *a, const __m128 b[4], float *out) {
__m128 result;
__m128 column = _mm_load_ps(a);
result = _mm_mul_ps(_mm_shuffle_ps(column, column, 0x00), b[0]);
result = _mm_add_ps(result, _mm_mul_ps(_mm_shuffle_ps(column, column, 0x55), b[1]));
result = _mm_add_ps(result, _mm_mul_ps(_mm_shuffle_ps(column, column, 0xaa), b[2]));
result = _mm_add_ps(result, _mm_mul_ps(_mm_shuffle_ps(column, column, 0xff), b[3]));
_mm_store_ps(out, result);
}
void matmult_SSE(float *A, const float *B) {
_MM_ALIGN16 float mA[16], mB[16];
#if DIFFERENT_ORDER
float *out = mA;
memcpy(mA, A, 16 * sizeof(float));
memcpy(mB, B, 16 * sizeof(float));
#else
_MM_ALIGN16 float out[16];
memcpy(mB, A, 16 * sizeof(float));
memcpy(mA, B, 16 * sizeof(float));
#endif
__m128 Bcolumns[] = {
_mm_load_ps(mB + 0),
_mm_load_ps(mB + 4),
_mm_load_ps(mB + 8),
_mm_load_ps(mB + 12)
};
lincomb_SSE(mA + 0, Bcolumns, out + 0);
lincomb_SSE(mA + 4, Bcolumns, out + 4);
lincomb_SSE(mA + 8, Bcolumns, out + 8);
lincomb_SSE(mA + 12, Bcolumns, out + 12);
memcpy(A, out, 16 * sizeof(float));
我太弱了，没有去成 WC 卡 T2，简直遗憾啊........
