基本介紹
- 中文名：卡常數
- 別名：卡常、底層常數最佳化
- 適用領域：信息學競賽(OI，ACM-ICPC)，程式設計套用
- 套用學科：計算機
- 使用前置技能：一定的代碼水平與對計算機機制的了解
- 拼音：kǎ cháng shù
名詞解釋,套用方法,相關題目,
名詞解釋
卡常數，又稱底層常數最佳化，特指在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起被棄用。
增強記憶體訪問連續性
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函式對整形每一個十進制位進行操作。
讀入最佳化：
對於無符號整數：
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時溢出的方法）：
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;
}
其他較高級方法
