常数优化技巧

常数优化技巧"/>

常数优化技巧

常数优化技巧

前言

在oi中，常数优化可谓极其重要
当然，不只是oi，常数优化一定程度上组成了代码风格
所以说，如何进行常数优化呢？
下面就简单的介绍我常用的几个常数优化技巧

#1习惯使用 const …

  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来举例：

	void gcd (const int a,const int b){if(b)return a;else return  gcd(b,a%b); }

相信很多人习惯于这种写法
但是又一个很严重的问题：在每次递归调用函数的时候,程序都会在栈中新建空间来存放递归函数里的变量，这无疑造成了极大的性能损失，不同于前一个，减少递归而使用迭代能够造成可观的优化。
所以说：

  int gcd(int a,int b){while(b){int t=a;a=b;b=t%b;}return a;}

#3习惯于将变量声明在循环外

定义变量意味着系统在内存条里找出一块地方让你存数据，想想cpu到内存条之间长长的距离 还有你那不怎么好的主板 特别是在使用AMD处理器（非Zen构架）的情况下
所以说对于上面 #2 的程序而言

  int gcd(int a,int b){int t;while(b){t=a;a=b;b=t%b;}return a;}

这样或许才是更优美的写法

#4 使用 inline

inline可以让你的非递归函数（此函数里不再调用其他函数）编译在原函数中而非另外开栈内存
所以对于 #3 的程序我们可以稍加修改

  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()中调用
这段代码就相当于

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和内存交互的速度。
能不能缩短这个距离呢？答案是肯定的。
别忘了我们的cpu里近1/2的面积都是缓存啊
直接把变量开在L3缓存里不就不用不远万里找内存条了嘛
所以：

	for(register int i=1;i<=MAXN;){i++;}

要比

	for(int i=1;i<=MAXN;){i++;}

快了将近十倍（亲测）

但有两点点要注意

其一：众所周知，CPU L3缓存很快，但也很小所以最多能够有让你开几个变量的空间，所以不要随意挥霍register
其二：如果你是在LUOGU这样的online judge网站上测试程序，那么我十分不建议使用register。
具体原因尚不清楚，但我猜测大概是由于服务器L3缓存使用频繁，很可能已经占满了，这个时候cpu可能又回去找内存条，耽误时间。

#6 正确使用STL库函数

STL慢是众所周知的事情，原因是STL中有大量的防止出错的检查项，拉低了速度
但即便如此STL函数的算法也是极其优秀的
例如你要求log2(5)。
一种方法是自己写二分法，复杂度是o(log§),p为精确位数，而STL中的log函数使用牛顿迭代，时间复杂度几乎是o(1)如果是这样不如选用STL。
然而，诸如 vector 一类的容器常数就非常的大，甚至于到了影响成绩的程度，尽量不要使用。
但是如果使用不当,就很容易对程序的性能造成负面影响

#7 访问连续内存（链表 NO！）

与其说这是个技巧不如说这是个思想
在图论当中，人们常常使用 链式前向星 或 邻接表 或 vector 来存储图
在这三者中，理论上vector的时间复杂度最低（只是理论上），因为观察使用方法不难发现前两者是链表结构，而vector是数组。
在内存当中，如果我们想要查询一个变量，就要进行寻址，而连续的内存可以大大降低寻址的时间复杂度（比如数组只需要寻址一次，查到数组第一个元素位置就能访问这个数组），而链表结构则需要反复寻址，效率低下。

#8 三目运算符

很不起眼的一个小东西，刚开始的时候我以为仅仅是用来简化代码的，后来发现它能带来巨量的性能增幅
例如在做 并查集 的时候需要的 find函数

int find(const int x){if(x==fa[x])return x;   else return fa[x]=find(fa[x]);
}

这一份代码已经十分优秀，但是：

int find(const int x){return x==fa[x]?x:fa[x]=find(fa[x]);
}

这一份代码在比较普遍的 1e5 规模的数据下能够带来100ms左右的性能提升。

#9 使用指针

这应该算是一个常识
之前看到有人写代码的时候这个样子

void A(int a[]){......
}

直接将数组作为参数传递给了函数
这是一个相当愚蠢的行为，就好比，别人向你借书，然后你把书抄了一份给他。
显然应当直接把书借给他。
所以只需要告诉函数该数组的位置就好了，其实就是把第一个元素的位置告诉函数（因为数组使用的是连续内存嘛）

inline void A(int *a){  for(int i=1;i<=n;i++){  ......	}
}

#10 读入优化&输出优化

很显然，任何一个题都需要输入输出，数据量大的话，至少要花费O(n)时间来读入（输出）数据。
其实读入（输出）优化的核心就是使用getchar();(putchar()😉。因为这两种方法是最快的读入（输出）函数。

代码：

快读：

  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;}

输出同理，因为不常用，就不附代码了。

#11 ++i与i++

实际上，经过我大量的实验发现，++i和i++实际表现上没有任何区别，甚至有时i++要更快。

#12 位运算 & 状态压缩

此二者内容颇多，便不细讲，附实例
位运算优化：【模板】线段树 1

#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

#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;	
}