理论层

循环展开

循环展开是一个非常好写而且增益极大的卡常方法，适用于大部分情况。

什么，你问bitset在哪，那玩意不仅常数小还稳定还好写已经升华为正解之流了。

循环展开是这个样子的：

比如你原来代码长这样

CPP

int ans=0;
for(int i=1;i<=n;++i){
	ans+=i;
}

循环展开一下就可以得到这个

CPP

int ans0=0,ans1=0,ans2=0,ans3=0,ans4=0,ans5=0,ans6=0,ans7=0;
for(int i=8;i<=n;i+=8){
	ans0+=i;
	ans1+=i-1;
	ans2+=i-2;
	ans3+=i-3;
	ans4+=i-4;
	ans5+=i-5;
	ans6+=i-6;
	ans7+=i-7;
}
switch(n&7){
	case 7:ans6+=n-6;
	case 6:ans5+=n-5;
	case 5:ans4+=n-4;
	case 4:ans3+=n-3;
	case 3:ans2+=n-2;
	case 2:ans1+=n-1;
	case 1:ans0+=n;
}

n=1e9(开O2)时，前一段代码需要680~920ms，后一段代码需要330~430ms，可以看出加成非常大。

前面的for把循环一拆八，促进指令级并发，从而提升效率

最后那个switch把一些漏掉的值补上，也可以换if等。这个东西不怎么需要卡常，因为一般运行次数不多。

指令级并发是指通过通过流⽔线等技术实现多条指令同时并⾏执⾏的并⾏技术，具体什么原理比较复杂，你只需要知道数据的相关性会影响指令级并发就可以了。

数据的相关性有很多种，你只要知道这几个会增加相关性就行了：

使用相同变量
前面语句的结果被后面用到

比如，你这么写循环展开：

CPP

int ans0=0,ans1=0,ans2=0,ans3=0,ans4=0,ans5=0,ans6=0,ans7=0;
for(int i=8;i<=n;i+=8){
	ans0+=i;
	ans0+=i-1;
	ans0+=i-2;
	ans0+=i-3;
	ans0+=i-4;
	ans0+=i-5;
	ans0+=i-6;
	ans0+=i-7;
}
switch(n&7){
	case 7:ans0+=n-6;
	case 6:ans0+=n-5;
	case 5:ans0+=n-4;
	case 4:ans0+=n-3;
	case 3:ans0+=n-2;
	case 2:ans0+=n-1;
	case 1:ans0+=n;
}

不开O2会慢，但O2会把for里一坨优化成ans0+=i+i-1+i-2+i-3+i-4+i-5+i-6+i-7;之类的，加上我的机子比较奇怪，跑的更快。

能合并还是要合并的，毕竟+=次数多了也影响常数。

卡常！

文章操作

理论层

循环展开

缓存

相关推荐

评论

卡常！