NOIP卡常数技巧

NOIP卡常数技巧
https://blog.csdn.net/a1351937368/article/details/78162078
http://www.mamicode.com/info-detail-2379526.html?tdsourcetag=s_pcqq_aiomsg
将上述两文内容进行合并如下：
1.IO优化
fread 和 fwrite ，如果还想再优化有mmap….(然而并不会用，好像也没用。。。)
读入优化(这个非常重要！！！！！！！)
inline int Read()
{
int x=0,f=1;char c=getchar();
while(c>‘9’||c<‘0’) {if(c==’-’) f=-1;c=getchar();}
while(c>=‘0’&&c<=‘9’) {x=x10+c-‘0’; c=getchar();}
return xf;
}
当然还有另一种但是这种只适用于读取非负数如下：
#inline int read(){
int num;
char ch;
while((ch=getchar())<‘0’ || ch>‘9’);
num=ch-‘0’;
while((ch=getchar())>=‘0’ && ch<=‘9’){
num=num*10+ch-‘0’;
}
return 0;
}
输出优化：
inline void out(int x){
if(x>=10){
out(x/10);
}
putchar(x%10+‘0’);
}
大家注意一下快速读入和快速输出尽量爆int的数据就尽量不要用了我原来用快速输出就WA掉了但是用printf就没有问题

2 inline
在声明函数之前写上inline修饰符（就像上面Read()一样），可以加快一下函数调用，但只能用于一些操作简单的函数。涉及递归，大号的循环等很复杂的函数，编译器会自动忽略inline。

3 register
在定义变量前写上register修饰符，用于把变量放到CPU寄存器中，适用于一些使用频繁的变量：register int n,m;
寄存器空间有限，如果放得变量太多，多余变量就会被放到一般内存中；
快，不是一般的快，快到什么程度呢？：
register int a=0;
for(register int i=1;i<=999999999;i++)
a++;
int a=0;
for(int i=1;i<=999999999;i++)
a++;
结果：
优化：0.2826 second
不优化：1.944 second
恐怖啊！！！！

4 循环展开
循环展开也许只是表面，在缓存和寄存器允许的情况下一条语句内大量的展开运算会刺激 CPU 并发(前提是你的 CPU 不是某 CPU)…
用法（下面是一个将一个(int) 类型数组初始化为(0)的代码段）：

void Init_Array(int *dest, int n)
{
int i;
for(i = 0; i < n; i++)
dest[i] = 0;
}
而如果用循环展开的话，代码如下:
void Init_Array(int *dest, int n)
{
int i;
int limit = n - 3;
for(i = 0; i < limit; i+= 4)//每次迭代处理4个元素
{
dest[i] = 0;
dest[i + 1] = 0;
dest[i + 2] = 0;
dest[i + 3] = 0;
}
for(; i < n; i++)//将剩余未处理的元素再依次初始化
dest[i] = 0;
}
循环引发的讨论
请看下面的两段代码，
代码1：
for(int i = 0; i < n; ++i)
{
fun1();
fun2();
}
代码2：
for(int i = 0; i < n; ++i)
{
fun1();
}
for(int i = 0; i < n; ++i)
{
fun2();
}
注：这里的(fun1())和(fun2())是没有关联的，即两段代码所产生的结果是一样的。

以代码的层面上来看，似乎是代码(1)的效率更高，因为毕竟代码(1)少了(n)次的自加运算和判断，毕竟自加运算和判断也是需要时间的。但是现实真的是这样吗？

这就要看(fun1)和(fun2)这两个函数的规模（或复杂性）了，如果这多个函数的代码语句很少，则代码(1)的运行效率高一些，但是若(fun1)和(fun2)的语句有很多，规模较大，则代码(2)的运行效率会比代码(1)显著高得多。可能你不明白这是为什么，要说是为什么这要由计算机的硬件说起。

由于(CPU)只能从内存在读取数据，而(CPU)的运算速度远远大于内存，所以为了提高程序的运行速度有效地利用(CPU)的能力，在内存与(CPU)之间有一个叫(Cache)的存储器，它的速度接近(CPU)。而(Cache)中的数据是从内存中加载而来的，这个过程需要访问内存，速度较慢。

这里先说说(Cache)的设计原理，就是时间局部性和空间局部性。时间局部性是指如果一个存储单元被访问，则可能该单元会很快被再次访问，这是因为程序存在着循环。空间局部性是指如果一个储存单元被访问，则该单元邻近的单元也可能很快被访问，这是因为程序中大部分指令是顺序存储、顺序执行的，数据也一般也是以向量、数组、树、表等形式簇聚在一起的。

看到这里你可能已经明白其中的原因了。没错，就是这样！如果(fun1)和(fun2)的代码量很大，例如都大于(Cache)的容量，则在代码(1)中，就不能充分利用(Cache)了（由时间局部性和空间局部性可知），因为每循环一次，都要把(Cache)中的内容踢出，重新从内存中加载另一个函数的代码指令和数据，而代码2则更很好地利用了(Cache)，利用两个循环语句，每个循环所用到的数据几乎都已加载到(Cache)中，每次循环都可从(Cache)中读写数据，访问内存较少，速度较快，理论上来说只需要完全踢出(fun1)的数据(1)次即可。
5 取模优化（仅O2）
//设模数为 mod
inline int inc(int x,int v,int mod){x+=v;return x>=mod?x-mod:x;}//代替取模+
inline int dec(int x,int v,int mod){x-=v;return x<0?x+mod:x;}//代替取模-
6 前置 ++
后置 ++ 需要保存临时变量以返回之前的值，在 STL 中非常慢。事实上，int 的后置 ++ 在实测中也比前置 ++ 慢 0.5 倍左右（UOJ 上自定义测试）
7 不要开bool，
所有bool改成char，int是最快的(原因不明)。
8 if()else语句比()?()

巴特西

NOIP卡常数技巧

最新文章

热门文章