OI常数优化技巧
前言
很多东西运行环境稍微变一下就不成立了。实话说常数优化意义不大。比如说洛谷的机器register加了比不加还慢。我感觉可能是寄存器不够了。这篇文章充分反应了我当时认识的浅薄@2023
在oi中，常数优化可谓极其重要
当然，不只是oi，常数优化一定程度上组成了代码风格
所以说，如何进行常数优化呢？
下面就简单的介绍我常用的几个常数优化技巧
#1习惯使用 const …
1
2
3
4
5
6
| const int inf=0x7fffffff;
void exgcd(int a,int b,int &d,int &x,int &y){
if(!b){d=a;x=1;y=0;return;}
exgcd(b,a%b,d,y,x);y-=x*(a/b);
}
|
const的最大作用就是减少参数传递的时间。
#2 不要递归！！
用基础算法算法gcd来举例：
1
2
3
4
| void gcd (const int a,const int b){
if(b)return a;
else return gcd(b,a%b);
}
|
相信很多人习惯于这种写法
但是又一个很严重的问题：在每次递归调用函数的时候,程序都会在栈中新建空间来存放递归函数里的变量，这无疑造成了极大的性能损失，不同于前一个，减少递归而使用迭代能够造成可观的优化。
所以说：
1
2
3
4
5
6
7
8
| int gcd(int a,int b){
while(b){
int t=a;
a=b;
b=t%b;
}
return a;
}
|
#3习惯于将变量声明在循环外
定义变量意味着系统在内存条里找出一块地方让你存数据，想想cpu到内存条之间长长的距离 还有你那不怎么好的主板 特别是在使用AMD处理器（非Zen构架）的情况下
所以说对于上面 #2 的程序而言
1
2
3
4
5
6
7
8
9
| int gcd(int a,int b){
int t;
while(b){
t=a;
a=b;
b=t%b;
}
return a;
}
|
这样或许才是更优美的写法
#4 使用 inline
inline可以让你的非递归函数（此函数里不再调用其他函数）编译在原函数中而非另外开栈内存
所以对于 #3 的程序我们可以稍加修改
1
2
3
4
5
6
7
8
9
10
11
12
13
| inline int gcd(int a,int b){
int t;
while(b){
t=a;
a=b;
b=t%b;
}
return a;
}
int main(){
cout<<gcd(4,8);
return 0;
}
|
比如在main()中调用
这段代码就相当于
1
2
3
4
5
6
7
8
9
10
11
| int main(){
int a=4,b=8;
int t;
while(b){
int t=a;
a=b;
b=t%b;
}
cout<<a;
return 0;
}
|
#5 register
前文中说到，每当你定义一个变量或函数，抑或修改变量维护数据，程序都会不远万里的请内存条帮你完成这项工作，而物理上cpu到内存插槽之间的距离一定程度也影响车cpu和内存交互的速度。
能不能缩短这个距离呢？
直接把变量开在寄存器里不就不用不远万里找内存条了
所以：
1
2
3
| for(register int i=1;i<=MAXN;){
i++;
}
|
要比
1
2
3
| for(int i=1;i<=MAXN;){
i++;
}
|
快了将近十倍（亲测）
但有两点点要注意
其一：CPU 寄存器很快，但也很小所以最多能够有让你开几个变量的空间，所以不要随意挥霍register
其二：register只是建议编译器将变量放在寄存器里。如果你是在LUOGU这样的online judge网站上测试程序，那么我十分不建议使用register。在luogu使用register不能获得性能提升，可能获得性能下降。具体原因尚不清楚。
#6 正确使用STL库函数
STL慢是众所周知的事情，原因是STL中有大量的防止出错的检查项，拉低了速度
但即便如此STL函数的算法也是极其优秀的
例如你要求log2(5)。
一种方法是自己写二分法，复杂度是o(log(p)),p为精确位数，而STL中的log函数使用牛顿迭代，时间复杂度几乎是o(1)如果是这样不如选用STL。
然而，诸如 vector 一类的容器常数就非常的大，甚至于到了影响成绩的程度，尽量不要使用。
但是如果使用不当,就很容易对程序的性能造成负面影响
#7 访问连续内存（链表 NO！）
与其说这是个技巧不如说这是个思想
在图论当中，人们常常使用 链式前向星 或 邻接表 或 vector 来存储图
在这三者中，理论上vector的时间复杂度最低（只是理论上），因为观察使用方法不难发现前两者是链表结构，而vector是数组。
在内存当中，如果我们想要查询一个变量，就要进行寻址，而连续的内存可以大大降低寻址的时间复杂度（比如数组只需要寻址一次，查到数组第一个元素位置就能访问这个数组），而链表结构则需要反复寻址，效率低下。
#8 三目运算符
很不起眼的一个小东西，刚开始的时候我以为仅仅是用来简化代码的，后来发现它能带来巨量的性能增幅
例如在做 并查集 的时候需要的 find函数
1
2
3
4
| int find(const int x){
if(x==fa[x])return x;
else return fa[x]=find(fa[x]);
}
|
这一份代码已经十分优秀，但是：
1
2
3
| int find(const int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
|
这一份代码在比较普遍的 1e5 规模的数据下能够带来100ms左右的性能提升。
#9 使用指针
这应该算是一个常识
之前看到有人写代码的时候这个样子
1
2
3
| void A(int a[]){
......
}
|
直接将数组作为参数传递给了函数
这是一个相当愚蠢的行为，就好比，别人向你借书，然后你把书抄了一份给他。
显然应当直接把书借给他。
所以只需要告诉函数该数组的位置就好了，其实就是把第一个元素的位置告诉函数（因为数组使用的是连续内存嘛）
1
2
3
4
5
| inline void A(int *a){
for(int i=1;i<=n;i++){
......
}
}
|
#10 读入优化&输出优化
很显然，任何一个题都需要输入输出，数据量大的话，至少要花费O(n)时间来读入（输出）数据。
其实读入（输出）优化的核心就是使用getchar();(putchar();)。因为这两种方法是最快的读入（输出）函数。
代码：
快读：
1
2
3
4
5
6
7
| template <typename _TP>
inline void read(_TP &X){
char ch=0;int w;X=0;
while(!isdigit(ch)){w=ch=='-';ch=getchar();}
while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
X=w?-X:X;
}
|
输出同理，因为不常用，就不附代码了。
#11 ++i与i++
实际上，经过我大量的实验发现，++i和i++实际表现上没有任何区别，甚至有时i++要更快。
#12 位运算 & 状态压缩
此二者内容颇多，便不细讲，附实例
位运算优化：【模板】线段树 1
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include <iostream>
#include <cstdio>
using namespace std;
const int inf=1e5+7;
template <typename _TP>
inline void read(_TP &X){
char ch;int w;X=0;
while(!isdigit(ch)){w=ch=='-';ch=getchar();}
while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
X=w?-X:X;
}
struct node{
int l,r;
long long sum,lag;
}t[inf<<2];
int a[inf];
inline void push_down(const int k){
t[k<<1].lag+=t[k].lag;
t[k<<1|1].lag+=t[k].lag;
t[k<<1].sum+=t[k].lag*(t[k<<1].r-t[k<<1].l+1);
t[k<<1|1].sum+=t[k].lag*(t[k<<1|1].r-t[k<<1|1].l+1);
t[k].lag=0;
}
void build(const int k,const int l,const int r){
t[k].l=l;
t[k].r=r;
if(l==r){
t[k].sum=a[l];
return;
}
int m=(l+r)>>1;
build(k<<1,l,m);
build(k<<1|1,m+1,r);
t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
}
void change(const int k,const int l,const int r,const int x){
if(t[k].l>=l && t[k].r<=r){
t[k].lag+=x;
t[k].sum+=x*(t[k].r-t[k].l+1);
return;
}
if(t[k].lag)push_down(k);
int m=(t[k].l+t[k].r)>>1;
if(l<=m)change(k<<1,l,r,x);
if(r>m)change(k<<1|1,l,r,x);
t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
}
long long ans;
void sum(const int k,const int l,const int r){
if(t[k].l>=l && t[k].r<=r){
ans+=t[k].sum;
return;
}
if(t[k].lag)push_down(k);
int m=(t[k].r+t[k].l)>>1;
if(l<=m)sum(k<<1,l,r);
if(r>m)sum(k<<1|1,l,r);
}
int main(){
long long n,x,l,r,q;
int opt;
read(n);read(q);
for(int i=1;i<=n;i++){
read(a[i]);
}
build(1,1,n);
while(q--){
read(opt);
switch(opt){
case 1:{
read(l);read(r);read(x);
change(1,l,r,x);
break;
}
case 2:{
read(l);read(r);
ans=0;
sum(1,l,r);
cout<<ans<<"\n";
break;
}
}
}
return 0;
}
|
位运算优化：【模板】树状数组 2
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
| #include <iostream>
#include <cstdio>
#define lowbit(x) (x)&-(x)
using namespace std;
const int inf=1e6+7;
int n,c[inf];
inline int sum(int p){
int ans=0;
while(p>0){
ans+=c[p];
p-=lowbit(p);
}
return ans;
}
inline void insert(int p,const int x){
while(p<=n){
c[p]+=x;
p+=lowbit(p);
}
}
int main(){
int m,opt,l,r,x,ox=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&x);
insert(i,x-ox);
ox=x;
}
for(int i=1;i<=m;i++){
scanf("%d",&opt);
switch(opt){
case 1 :{
scanf("%d%d%d",&l,&r,&x);
insert(l,x);
insert(r+1,-x);
break;
}
case 2 :{
scanf("%d",&x);
cout<<sum(x)<<"\n";
break;
}
}
}
return 0;
}
|
