1. 优化类

1. 读入 / 输出优化

这个其实优化效果不大

1. 关闭同步 & tie

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

可以加速 cin/cout，代价是不能使用 scanf/printf 及其他的 <stdio.h> 库中包含的 IO 函数

解释：

1. 第一句：关闭同步，也就是不兼容 C
2. 第二句：解除 cin/cout 的同步，这样每次 cin 不用都 flush 一下 .

2. 快速读入（快读）

思想是用 getchar() 一个字符一个字符的读

3. 快速输出（快输）

思想是用 putchar() 一个字符一个字符的输

4. fread/fwrite 优化

我们可以模拟标准的读入，创建一个 buffer 缓冲区，fread 可以更快的读入多个字符，重定义 getchar() 就可以啦

对应的，我们也有 fwrite 函数，可以更快的输出多个字符 .

5. 其他技巧

多个数的读入可以用缺省参数来实现

不同类型的读入可以用 template 实现

2. 利用局部性

局部性是指程序倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身 . 局部性分为时间局部性和空间局部性

比如在循环的时候，编译器也无法预测下一次的 \(i\) 会不会变成什么奇怪的东西，所以它只能一个步骤一个步骤的执行 .

那么我们可以明确告诉它接下来的几个操作中所要用到的 \(i\) 与现在的 \(i\) 有什么关系。从而让它能够知道接下来该干什么，刺激 CPU 并发，也就是循环展开 .

1. 循环展开

前面讲了原理了，给个示例：

ll sum=0;
for (int i=1;i<=n;++i)sum+=a[i];
return sum;
// 不如：
ll sum1=0,sum2=0,sum3=0,sum4=0,sum5=0,sum6=0,sum7=0,sum8=0;
// 1. 不要只弄一个 sum，这样不能并发
for (int i=0;i+8<=n;i+=8)
{
	sum1+=a[i+1]; // 2. 不要用 ++i，不要改变 i 的值
	sum2+=a[i+2];
	sum3+=a[i+3];
	sum4+=a[i+4];
	sum5+=a[i+5];
	sum6+=a[i+6];
	sum7+=a[i+7];
	sum8+=a[i+8];
}
switch (n&7)
{
	case 7: sum7+=a[n-6];
	case 6: sum6+=a[n-5];
	case 5: sum5+=a[n-4];
	case 4: sum4+=a[n-3];
	case 3: sum3+=a[n-2];
	case 2: sum2+=a[n-1];
	case 1: sum1+=a[n]; 
}
return sum1+sum2+sum3+sum4+sum5+sum6+sum7+sum8;

一般来说，循环展开只需要展开 6~8 层就已经够了，多了的话可能造成寄存器溢出从而反使程序的运行速度变慢 .

2. 重新结合变换

也就是把类似的放在一起

for (int i=1;i<n;i++) ans=(ans+a[i])+a[i+1];
// 不如
for (int i=1;i<n;i++) ans=ans+(a[i]+a[i+1]);

3. 卡 cache/寄存器

我们知道，cache/寄存器 里存储的数据访问是非常快的

高速缓存器里面存了一段内存的东西，可以通过高速缓存器快速访问这段内存里面的任何一个元素

一旦访问内存外的元素，cache 就会看情况选择是否清空并重新装填内存，就会花费时间

总的来说，就是不要让 cache「溢出」

比如基排 \(2^8\) 为基数就比 \(2^{16}\) 为基数快，因为 \(2^8\) 能卡进 cache .

寄存器同理

4. 杂

1. x[a] 是比 *(x+a) 慢的
2. bool 型的东西可以压位，注意善用内建（builtin）函数 .

一些小技巧

原文：https://www.cnblogs.com/CDOI-24374/p/14842503.html