卡常数
添加时间：2024-08-12
卡常数，又称底层常数优化，特指在OI/ACM-ICPC等算法竞赛中针对程序基本操作进行的底层优化，一般在对程序性能要求较为严苛的题目或是在算法已经达到理论最优时间复杂度时使用，有时也用于非正解的强行优化。实现方法有使用register寄存器关键字、利用空间连续性使数组进入缓存、输入输出优化等。
register关键字的使用
register是C++关键字，将其加在变量声明前可以建议编译器将变量直接放入寄存器中，从而大量减少该变量访问时间。
即将形如
for(int?i=1;i<=n;i++)
的语句改为
for(register?int?i=1;i<=n;i++)
该关键字只起到建议的作用，并不能保证变量一定被放入寄存器，且CPU中寄存器数量有限，建议将其加到循环变量等常用变量中，以免造成负优化。
该关键字从C++17起被弃用。 [1]
增强内存访问连续性
CPU在运行时，会按照“当一个变量被访问，其周围的变量接下来很有可能会被访问”的原则，将一定数量的变量存入高速缓存。故在使用高维数组时，应尽量使最后一维变化连续。
for(int?i=1;i<=n;i++)
for(int?k=1;k<=p;k++)
for(int?j=1;j<=m;j++)
ans[i][j]+=a[i][k]*b[k][j];
会比
for(int?i=1;i<=n;i++)
for(int?j=1;j<=m;j++)
for(int?k=1;k<=p;k++)
ans[i][j]+=a[i][k]*b[k][j];
要快，因为第一种做法使得b[k][j]的访问相较于第二种更为连续。
输入输出优化
也有针对浮点数的版本。
原理：用getchar与putchar函数对整形每一个十进制位进行操作。
读入优化：
对于无符号整数： [2]
void?read(int?&x)
{
x=0;register?char?c=getchar();
while(c<48||57<c)?c=getchar();
for(;48<=c&&c<=57;c=getchar())?x=x*10+(c&15);
}
使用时调用read(n);
对于有符号整数（避免在读入-2147483648时溢出的方法）： [3]
int?redi(void)?{
int?f?=?0;char?ch,?flag?=?0;
while(ch?=?getchar(),?!isdigit(ch))?if(ch?==?'-')?flag?=?0xff;
if?(flag)?{
?while?(isdigit(ch))?f?=?f?*?10?-?ch?+?48,?ch?=?getchar();
}?else?{
?while?(isdigit(ch))?f?=?f?*?10?+?ch?-?48,?ch?=?getchar();
}
return?f;
}
其他较高级方法
- 1.
- 2.指令集函数：使用CPU中自带指令代替部分函数，起到超高速计算的效果。
- 3.
- 4.
1式：
- 1.
- 2.WC2017 挑战：由著名的卡常数选手王逸松命题，卡常数界宗师级的题目。在2017年的冬令营上让无数选手苦思冥想，并在其中提出了“松式基排”的概念。因此OI选手也将极其优秀的复杂度称为O(wys)。
