随机化 时间戳优化 位运算 bitset 状态压缩

OI 优化技巧

快读快写,卡常,清空,mt19937

Posted by TH911 on December 31, 2024

快读快写

scanf 与 printf

没什么好说的。

关闭同步流与解除绑定

众所周知，cin 与 cout 的 IO 效率十分低下，主要原因就是因为需要兼容 C 的 scanf 和 printf 以保证线程安全而不混乱。

我们以下代码来关闭同步流并解除绑定：

1
2

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

cin.tie() 指向的是 cin 绑定的函数的指针；默认情况下指向 &cout。 也就是说，在默认情况下，每次 cin 之后都会调用 cout.flush() 来刷新缓冲区。这样的好处就是能够保障你在 cin 之前 cout 的数据会在 cin 之前显示。 但是，这样的坏处就是效率低下。 因此我们可以将其指向 nullptr 或者 NULL、0（空指针）以避免每次都调用 cout.flush() 拉低效率。

getchar 与 putchar

我们可以通过 getchar() 来较为高效的读入一个字符，通过 putchar() 来较为高效的输出一个字符。

因此我们就可以手写 IO 函数以加速输入输出。

整型 IO 参考代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

template<typename T>
inline void Read(T &x){
	x=0;
	register int f=1;
	register char ch=getchar();
	for(;ch<'0'||'9'<ch;ch=getchar())if(ch=='-')f=-1;
	for(;'0'<=ch&&ch<='9';ch=getchar())x*=10,x+=ch-'0';
	x*=f;
}
template<typename T>
inline void Write(register T x){
	static char s[1001]={};
	static int top=0;
	if(x<0){
		putchar('-');
		x=-x;
	}
	do{
		s[top++]=x%10+'0';
		x/=10;
	}while(x);
	while(top)putchar(s[--top]);
}

在输入 n 时，Read(n); 即可；输出 n 时 Write(n); 即可。

对于浮点型，可以参照以上代码修改。

getchar_unlocked 与 putchar_unlocked

有些时候，getchar 和 putchar 的效率仍然太过于低下，因此在 Linux 下可以使用 getchar_unlocked 与 putchar_unlocked 来加速。

这两个函数的效果其实就相当于在声明函数前加了个 inline 来内联，最终效率会接近 fread 与 fwrite。

一种简单的方式

因为在 Windows 下并不存在 getchar_unlocked 和 putchar_unlocked，因此在 Windows 下写代码时使用的都是 getchar 和 putchar。但是放在 Linux 评测机下时，这两个函数时可用的。

因此，我们可以在代码中使用 getchar 和 putchar，并在提交时加上两行代码： 

1
2

#define getchar getchar_unlocked
#define putchar putchar_unlocked
这样，在调试时注释掉这两行代码即可。

fread 与 fwrite

fread、fwrite 是两个可以一次性 IO 大量数据的函数。

使用方法如下：

1
2

std::size_t fread(void* buffer, std::size_t size, std::size_t count,std::FILE* stream);
std::size_t fwrite(const void* buffer, std::size_t size, std::size_t count,std::FILE* stream);

fread(buf,1,1<<20,stdin) 表示从 stdin 读入大小为 1<<20 字节的数据到 buf 中，每个数组元素的大小为 $1$ 字节；其中 buf 是一个自行声明的数组。

对应的 fwrite(pbuf,1,1<<20,stdout) 表示将 pbuf 中的前大小为 1<<20 字节的 $1$ 个字符为一个元素的数据输出到 stdout。

这个 $1$ 是有意义的，并非所有数据类型都是 $1$，例如 wchar_t（宽字符）就应该是 $2$。

因此，对于输入我们仅仅需要重新定义一个函数实现 getchar 的功能然后沿袭 getchar 优化的逻辑即可。

fread 优化参考代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

inline char gc(){
	static int p1,p2;
	static char buf[1<<20];
	if(p1==p2)p1=0,p2=fread(buf,1,1<<20,stdin);//初始/缓冲区用完时应当更新fread以IO数据 
	if(p1==p2)return EOF;
	return buf[p1++];
}
template<typename T>
inline void Read(T &x){
	x=0;
	T f=1;
	char ch=gc();
	for(;ch<'0'||'9'<ch;ch=gc())if(ch=='-')f=-1;
	for(;'0'<=ch&&ch<='9';ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	x*=f;
}

同样地，对于字符串可以很容易地自行定义输入函数；对于浮点型，可以参照修改。

fwrite 优化的输出代码有个细节需要注意。那就是要记得在程序结束时刷新输出缓冲区。

尽管可以在程序的结束出口前手动 fwrite 来刷新，但是我们可以使用一种更方便的方法。

我们定义一个结构体或者类，定义其析构函数来 fwrite 刷新缓冲区即可。这样在程序结束析构时，就会自动刷新。

fwrite 优化参考代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int p;
char pbuf[1<<20];
inline void flush(){
	fwrite(pbuf,1,p,stdout);//刷新缓冲区 
	p=0;
}
struct tool{
	~tool(){
		flush();//析构函数 
	}
}tool;
inline void Write(char ch){
	pbuf[p++]=ch;
	if(p==(1<<20))flush();
} 
template<typename T>
inline void Write(T x){
	if(x<0){
		Write('-');
		x=-x;
	}static char s[101];
	int top=0;
	do{
		s[++top]=x%10^'0';
		x/=10;
	}while(x);
	while(top)Write(s[top--]);
}
总代码

此处实现采用的是数组访问的形式，如若使用指针会更快一些。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

namespace IO{
	inline char gc(){
		static int p1,p2;
		static char buf[1<<20];
		if(p1==p2)p1=0,p2=fread(buf,1,1<<20,stdin);
		if(p1==p2)return EOF;
		return buf[p1++];
	}
	template<typename T>
	inline void Read(T &x){
		x=0;
		T f=1;
		char ch=gc();
		for(;ch<'0'||'9'<ch;ch=gc())if(ch=='-')f=-1;
		for(;'0'<=ch&&ch<='9';ch=gc())x=(x<<3)+(x<<1)+(ch^48);
		x*=f;
	}
	int p;
	char pbuf[1<<20];
	inline void flush(){
		fwrite(pbuf,1,p,stdout);
		p=0;
	}
	struct tool{
		~tool(){
			flush();
		}
	}tool;
	inline void Write(char ch){
		pbuf[p++]=ch;
		if(p==(1<<20))flush();
	} 
	template<typename T>
	inline void Write(T x){
		if(x<0){
			Write('-');
			x=-x;
		}static char s[101];
		int top=0;
		do{
			s[++top]=x%10^'0';
			x/=10;
		}while(x);
		while(top)Write(s[top--]);
	}
}
using IO::Read;
using IO::Write;

多测与清空

fill 与 memset

首先，如果每次清空都 memset 整个数组的话，可能会超时。因此，我们可以只 fill 部分。

但需要注意的是，memset 同样可以只清空部分数组，这具体就涉及到了计算。

比如说给定 int 数组 a，大小为 $1000$，那么数组 a 的大小就是 $4\text{Byte}\times 1000=4000\text{Byte}$。

此时我们若只想清空前 $200$ 个元素，可以使用 fill(a,a+200,0)，也可以使用 memset(a,0,800)。

一般的清空整个数组的 memset 是这样的：memset(a,0,sizeof(a))。这表示清空 a 的前 sizeof(a) 个字节的数据。

但是我们清空前 $800$ 个字节，每个元素正好是 $4$ 字节，也就是前 $200$ 个元素。

时间戳优化

时间戳优化可以通过 $\mathcal O(n)$ 的空间复杂度来实现时间复杂度 $\mathcal O(1)$ 的清空。

这在树状数组中提到过，具体而言就是对于需要清空的数组 $a$ 定义数组 $tag$，$tag[i]$ 表示 $a[i]$ 是否是当前测试数据的数据。比如说定义了一个 $t$ 表示当前测试数据编号，清空就仅仅需要令 $t\leftarrow t+1$ 即可。

常数优化

register 与 inline

这俩东西在新版 C++ 里没用了，仅仅为了向下兼容才存在。

简而言之，是因为这些你不用脑子都能想到的优化编译器早想到了，用了你的反而会更慢。

然而，存在例外。参见此处，编译器有时可能不会自动 inline，从而导致效率低下。建议一律手动 inline。

内存跨度

以线段树为例。

维护线段树的节点信息到底应该是开一个 struct 存储 .l、.r、.value、.tag，还是开四个数组访问 l[i]、r[i]、value[i]、tag[i] 呢？

在数据规模较小的情况下，区别不大。因为评测机波动，谁更快一些没有定论。

但是当数据规模较大时，开一个 struct 会更快一些。

计算机的信息抓取

之所以会更快一些，主要是因为当你访问一个变量时，计算机会抓取内存上其附近的值。

很明显在线段树中同一个节点的值几乎会连续用到，因此开一个 struct 会快一些。

去除递归

转栈或递推。

比如说快速幂。

位运算

位运算比 +、-、*、/ 要快很多，因此可以使用。

运算优先级

使用位运算应当注意运算优先级。位运算的优先级非常低，甚至低于比较运算符 ==，几乎仅次于 ,。因此建议加上括号。

比如说 1+2<<3，那么结果就是 3<<3，即 $24$。

  • x*10：(x<<3)+(x<<1)。
  • x+18 或 x-48：这主要是在快读快写中使用，可以优化为 ^48。
  • x*2：x<<1。
  • x/2：x>>1。
  • x*2+1：x<<1|1；这其实在线段树中用得较多。
  • ……

while 与 if

在计算机中，if 被更加倾向于会执行，while 会被更加倾向于不被执行。

这样的后果就是计算机每次会抓取 if 内的信息，然而若是这个 if 执行的次数少之又少，就会造成时间浪费。

因此我们可以对于这种 if 将其改为 while 和 break。

火车头优化（指令集优化）

所谓火车头优化，其实就是在代码前堆上一堆开启优化的指令。

但是据说在 NOI 系列赛事中被禁用了……

所以，慎用。可以在日常 OJ 上使用。

火车头优化完整代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#pragma GCC optimize(3)
#pragma GCC target("avx")
#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")
#pragma GCC optimize(2)

随机化

mt19937

生成随机数可以使用 rand()，然而自带的 rand() 效率较低且值域较小。

因此我们可以使用 mt19937 来生成随机数：

1

mt19937 Rand(time(0));

这样，在需要随机数时使用 Rand() 即可（time(0) 是为了做种）。

注意：尽量包含头文件 <random>，否则 可能 报错。

mt19937 与头文件 random

在 Windows 下 Dev-C++5.11 内使用 C++14 编译运行，不带头文件 random可以正常编译运行。然而在 Linux 下或洛谷 IDE 下，则可能会报错。

因此建议加上头文件 random 或使用万能头文件 bits/stdc++.h。

否则可能就会 $\color{red}\text{CE}$。

shuflle

通过 shuffle 可以很容易的打乱一个数组的顺序。同上，建议添加头文件 <random>。

使用格式：

1

shuffle(order.begin(),order.end(),Rand);

order.begin() 是数组的起始指针，order.end() 是数组的末尾指针，Rand 是随机函数。

建议将 Rand 设置为 mt19937 的，效率更高。

对数：__lg 与 lg[i] 预处理

对于取以 $2$ 为底的对数的时候，我们可以使用 <cmath> 库中自带的 log2 函数来求解，例如 log2(5) 就是 $2.32193$。

然而有些时候，我们仅仅需要整数部分，并不需要小数点后那么多位，因此我们考虑优化。

  1. 重写对数函数

    很简单，复杂度也就是 $\mathcal O(\log n)$。

    1
2
3
4
5

    int lg(int n){
	int ans=0;
	while(n>>=1)ans++;
	return ans;
}

    但是，我们可以使用 GCC 提供的非标准函数 __lg。

    比如 __lg(16) 就是 $4$，__lg(15) 就是 $3$。

  2. 数组预处理

    主要是递推。

    定义数组 $lg$，$lg[i]$ 表示 $\left\lfloor\log_2 i\right\rfloor$ 的值，也就是 $i$ 在二进制上最高位的位权的对数。

    递推关系式：

    \[lg[i]=lg\left[\dfrac{i}{2}\right]+1\]

    递归边界：

    \[lg[0]=0\]

    也很简单，就是右移一位得到的数的位权对数加 $1$ 的结果。

    代码：

    1

    for(int i=1;i<=N;i++)lg[i]=lg[i>>1]+1;

状态压缩：bitset

需要包含头文件 <bitset>。

对于一长串 bool 变量，明明只使用了 $1\text{bit}$，但是却占用了 $1$ 字节，非常不合理。

因此我们可以通过 bitset 来解决。

bitset 来进行状态压缩会将时间复杂度降为原来的 $\dfrac1w$，$w$ 表示计算机字长，通常为 $64$ 或 $32$。

使用方法

  • 创建

    1

    bitset<N+1>p;

    创建了一个 $N+1$ 位的 bitset $p$。

  • 查询 bitset 内 $1$ 的个数

    1

    p.count();

  • 将 bitset 内第 $i$ 位设置为 $1$

    1

    p.set(i);

  • 位运算

    bitset 之间如二进制数般可以进行位运算，位运算的结果仍然是一个 bitset。

    如：

    1

    (p[i]&p[j]).count();

常用技巧

邻接表下无向边作两条有向边存储时查找反向边

可以从 $2$ 开始存储边，无向边的两条有向边相邻，因此可以使用异或 $1$ 来查找反向边。

比如这里。

memset 初始化

  • $+\infty$：0x3f 或 0x7f。

    0x3f 保证相加之后不会爆 int，实际为 $1061109567\approx10^9$。

  • $-\infty$：0x80。

    0xc0 保证相加之后不会爆 int，实际为 $-1061109568\approx-10^9$。

数据结构优化

线段树

线段树层数

  • 线段树的上 $5$ 层可以直接砍掉，因为很少，可以暴力遍历。
  • 线段树的下 $5$ 层可以直接砍掉，可以暴力维护信息。

区间端点

当维护信息较少时，不建议在结构体内维护区间端点，因为会破坏内存访问的连续性。

CATALOG
    FEATURED TAGS
    树状数组 题解 提高+/省选− 省选/NOI− DP 普及+/提高 基础算法 数学 组合数学 普及/提高− 贪心 字符串 线段树 未完 图论 平衡树 数论 树形 DP 搜索 Tarjan Trie 二分 位运算 二分答案 状态压缩 FHQ Treap 前端 无聊时候的一点思考 最短路 树链剖分 NOI/NOI+/CTSC
    FRIENDS