浅谈卡常
_H17_
·
2024-08-07 21:02:50
·
算法·理论
零、什么是卡常
卡常数，又称底层常数优化，是信息学竞赛中一种针对程序基本操作进行空间或时间上优化的行为，与时间复杂度或剪枝有别。
也指程序虽然渐进时间复杂度可以接受，但是由于实现/算法本身的时间常数因子较大，使得无法在 OI/ACM-ICPC 等算法竞赛规定的时限内运行结束。——百度百科
简单的来讲，时间复杂度是不考虑常数的，同样的时间复杂度（如 O(n)）的常数、运行时间也是有区别的。例如 100n+10 也是 O(n)，我们可以粗略的理解为卡常就是尽量把代数式的常数项减少。
当然，有时我们也要考虑通过编译、电脑（CPU）等的利用来进行优化。
一、从输入输出开始
流输入输出
下文默认省略 iostream 的 std::，即默认加入了 using namespace std; 语句。
最常见的输入、输出方式一定是 cin,cout，这也是几乎每个人接触 OI 时会学的输入、输出。
这种方式（iostream 方式，即流输入输出）是最好写的输入输出（通常情况下），但也很慢。
为什么很慢？C++ 语言，是在 C 语言的基础上实现的，仍然保留着 C 的 stdio（见下文【标准输入输出】）。但是想象一下，输入、输出是个搬运活，stdio 和 iostream 分别是两位工人，老板会派给他们任务，任务的形式是“读入第一个未读入的值”，显然如果两位工人不交流会重复搬运，所以 stdio 和 iostream 是同步的，每次从 iostream 中读取数据都要和 stdio 同步一次，这也是为什么 iostream 慢的原因。
注意由于 stdio 出现时并没有 iostream，所以是 iostream 同步的 stdio，所以 stdio 这些比较快。
慢，怎么办？懒人肯定不想写长长的 stdio（非必要情况），所以我们可以通过 ios::sync_with_stdio(false); 来解除和 stdio 的同步。同样可以使用 cin.tie(0),cout.tie(0); 解除 cin,cout 之间的同步。
注意：解除绑定后两者不能同时使用，不理解可以看上文“搬运工”的例子。
同样，使用 cerr 调试之后记得注释掉调试语句再提交，cerr 也会造成缓冲区刷新。
换行时尽量使用 '\n' 而非 endl，原因是 endl 自动刷新了缓冲区。
通常情况下，不刷新缓冲区没有问题，但是遇到特殊情况（如交互题输入、输出），请使用 cout< 标准输入输出 该内容在 C 内基本全部兼容，不会自动同步 iostream 的内容，所以无需解绑同步，速度相对较快。 最常用的标准输入输出 scanf,printf 语句和优化后的 iostream 相差不多，主要耗时在格式串的判断上，不特意卡基本够用。 非常快的标准输入输出 getchar,putchar 规避掉了 scanf,printf 的格式判断问题，我们可以根据题目的输入来使用、判断。 但是需要写通常快读函数来读入数（字符串等通常可以 getchar 并拼接）。 代码： int read(){ char c; int x=0,f=1; while('0'>(c=gc())||c>'9')//非数字 if(c=='-') f=-1;//判断负数 while('0'<=c&&c<='9')//是数字 x=(x<<3)+(x<<1)+(c^48),c=gc();//按位累加 return x*f; } 带有“按位累加”的板块涉及位运算，详见【位运算】，简单解释一下：(2^3+2^1)=10 代表十进制左移一位，c^48 是二进制异或，48 是字符 '0' 的 ASCII 码，为什么用异或替代减法？48 是 16 的倍数，二进制后四位都是 0 ，而数字只有 0\sim 9，不需要 4 位的二进制，不会越界。 快写也是类似的拆位，这里不详细阐述。 当然如果数据位正数可以去掉负数判断。 更快？ 使用 getchar_unlocked,putchar_unlocked 替代上述的 getchar,putchar，弊端是不是线程安全，本地（Windows）可能不能过编译。 如何解决上述弊端？使用 fread,fwrite 来替代。 函数 fread 的定义代码：size_t fread( void *restrict buffer, size_t size, size_t count, FILE *restrict stream );（当然已经定义在 cstdio 中了），buffer 指缓冲区，size 是单次读入大小，count 是读入数量，stream 是文件。 调用示例 fread(buf,1,100000,stdin);，它将返回读入元素数量。 如何用 fread 进行字符读入操作？ 代码： char gc(){ static char buf[100001],*p1=buf,*p2=buf; return(p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++); } static 表示函数除第一次调用外不会重置，定义在全局变量部分，避免空间超出。 返回的东西比较奇怪： 应该满足 p1,p2 指向同一个位置； p1 设置位 buf，即缓冲区起点（也可以理解为读入前的指针位置），p2=p1+fread(...) 也就是 p2 表示读入完之后的指针（因为起点加长度等于终点）。 如果 p1,p2 相等，那么说明没能成功读入，返回 EOF 表示文件结束，否则返回读入的第一个字符也就是 p1，并让 p1 增加。 也可以将其变成宏定义的方式减少函数调用。 size_t fwrite(const void* buffer, size_t size, size_t count, FILE* stream); 类似于 fread，使用示例：fwrite(obuf,1,cnt,stdout);，返回成功输出的字符数量。 其他很快的读入、输出（差不多我就不一一讲了）：getc,fgetc,putc,fputc，参数要比 getchar,puchar 多加一个文件（通常是 stdin,stdout） 习题 【模板】快速读入。 二、宏定义、函数、常量、只读 宏定义类似于“代码替换”，建议将简单函数替换为宏来调用以降低时间开销，速度最快。 注意：例如 #define MAX(x,y) (((x)>(y))?(x):(y))时，如果调用 MAX(ans,dfs(1,0)) 会重复执行。要小心这种情况。 函数比较稳定，不如宏定义那么容易出错，但是调用开销较大。 为了解决上述问题，大家通常使用 inline，但是编译器会自动识别函数，而且 inline 只是作为建议，效果不大。如果要强制内联，请使用 __inline。 注意：__inline 尽量少用，容易造成负优化。 当然所谓的寄存 register 也是建议，C++17 索性取消了。 常量的声明方式是 constexpr，而“只读”的限制才是 const，用 const 代表常量只有防止误修改的作用，建议不要这么做。 而且 constexpr 速度略快于 const。 三、判断 判断语句分为 if,else、switch,case 和三目运算符。 其中简单语句建议使用三目运算符，简单明了，速度快。 复杂的尽量使用 switch,case，它的速度快于 if,else。 有时候 if,else 和 switch,case 略强于三目运算，详见【冷热代码】。 四、避免除法、取余 它们虽然属于 C++ 的基本算数运算，但是还是常数很大的，尽量合并同类项避免除法。 在保证正确性的情况下可以尽量少取余。 五、位运算 位运算是二进制的位进行的运算，由于计算机使用二进制存储，速度会快很多。 常见技巧 &1 替代 %2，通过 x< 也有时会用到或、异或、取反（分别是 |,^,~）。 优先级可以自己查查，但是强烈建议加括号！不然某些编译器可能让你死的很惨。 也可以类似状态压缩，把很多位压成一个 k 进制数，通常 k=2。 注意求 popcount 这种没有自带的，手写一般比 __builtin 家族要慢。 六、STL 优化？extc++ 的 pb_ds？ 基本上加上 O2 速度都很快，非必要可以换成手写。 但是 map 这个东西的复杂度是 O(\log n)，但是 pb_ds 中 gp_hash_table,cc_hash_table 的复杂度是 O(1)，功能几乎相同。 建议使用 gp_hash_table,map，非必要不要用别的，不过哈希有很小概率被卡掉。 以及 bool 数组可以用 bitset 进行类似压位的优化（也可以进行 __int128 的压位）。 附：pb_ds 需要头文件 bits/extc++.h，名称空间通常是 __gnu_pbds。 注：压位不止节省空间，同样节省时间，因为运算数量变少，类似于块长较小的分块。 七、常见 CPU 底层卡常 循环展开 最典型的莫非是循环展开了，评测机 CPU 通常是多核，展开之后可以促进 CPU 并发。 通常把循环展开为 8，过多会导致负优化。 如求和等操作尽量使用不同的变量进行，最后汇总。 这样降低了数据相关性，提高了速度。 Cache 命中率提高 Cache 的速度非常快，但是空间非常小，命中率是关键部分。 可以让一段时间内只访问一小部分的变量提高命中率，开小一点空间等。 八、遍历数组顺序 顺序遍历比非顺序遍历速度要快的多，顺序遍历指每一维（从高到低）都从小到大遍历，这样内存之间差距小，跳转快。 有时候也可以使用指针运算提高速度。 矩阵乘法、Floyd、DP 有时候适用。 不要因为懒、代码不美观省去这个，这个还是比较重要的。 九、冷热代码 什么是冷代码？什么是热代码？经常执行的就是热代码，很少执行的就是冷代码。 你可能要问为什么会有是否经常执行，首先循环内的代码经常执行，if 中有可能一半一半，也有可能有极小概率才执行、不执行。 编译器会自动预处理一些简单的 if 中的代码，其中包括冷代码，这也是 __inline 负优化的原因。 当然封装成函数、换成 while(...){...break;} 也可以处理冷代码。 我们也可以使用 __builtin_expect(条件,条件期望值) 来表示这段代码是冷、热，返回值是条件真假。 示例： for(int i=1;i<=n;i++){ if(__builtin_expect(i==7,0)) cout<<"Lucky.\n"; cout< } 显然，i==7 是个极小可能出现的条件，所以期望是假，可以加快速度，也可能会有负优化（估计错误、数据卡掉）。 特别地 C++20 加入了 [[likely]],[[unlikely]]。 使用 C++20 上述代码可以写为： for(int i=1;i<=n;i++){ if(i==7)[[unlikely]] cout<<"Lucky.\n"; cout< } 十、其他 int,char 速度比其他类型基本要快。同样的类型一般无符号快（这个比较有用，循环变量也可以改）； 尽量不递归，写循环； 某些 STL 不能乱用，常数太大。大部分都还是可以接受的。 评测点分治，听起来很高大上，其实就是对不同数据范围的评测点分开处理。比如带有除以二的，临时换成右移一位。 以上部分内容会被编译器自动识别并优化。 十一、玄学 评测机有波动，可以多交几次卡过去。 尝试换代码编译器 GCC9 或者不用 GCC9 都试验一遍（注意：通常一点效果没有，但是偶尔会卡大约 10 倍的时间！） 可以使用随机化，但是通常是在反正也过不去，碰运气的情况下改变搜索、遍历等的顺序，当然 SPFA 的堆、双端队列等也是这样的优化。 示例 三元上升子序列。 代码（暴力 DP）： #include #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2") #define UNSIGNED using namespace std; char buf[(1<<10)+1],*p1=buf,*p2=buf; #define gc() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<10,stdin),p1==p2)?-1:*p1++) /*__inline char gc(){ #ifndef EDIT_BUF static constexpr int buf_num=1e5; #else static constexpr int buf_num=EDIT_BUF; #endif static char buf[buf_num+1],*p1=buf,*p2=buf; return(p1==p2&&(p2=(p1=buf)+fread(buf,1,buf_num,stdin),p1==p2)?EOF:*p1++); }*/ __inline unsigned int read(){ char c; unsigned int x=0; while('0'>(c=gc())||c>'9'); while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=gc(); return x; } __inline void write(unsigned long long x){ constexpr int N=25; static char buf[N]; static int tot=-1; while(x) buf[++tot]=x%10+48,x>>=1,x/=5; for(unsigned int i=0,j=tot;i swap(buf[i],buf[j]); fwrite(buf,1,tot+1,stdout); return; } constexpr unsigned int N=3e4+5; unsigned int n,a[N]; unsigned int f[N]; unsigned long long ans,ans1,ans2,ans3,ans4,ans5,ans6,ans7,ans0; signed main(){ n=read(); for(unsigned int i=1;i<=n;++i) a[i]=read(); for(unsigned int j=2,k,t,sum0,sum1,sum2,sum3,sum4,sum5,sum6,sum7;j sum0=sum1=sum2=sum3=sum4=sum5=sum6=sum7=0,k=1; if(j<7){ goto g;} t=j-7; for(;k sum0+=(a[k] sum1+=(a[k+1] sum2+=(a[k+2] sum3+=(a[k+3] sum4+=(a[k+4] sum5+=(a[k+5] sum6+=(a[k+6] sum7+=(a[k+7] } g: f[j]=sum0+sum1+sum2+sum3+sum4+sum5+sum6+sum7; switch(j-k-1){ //case 7:f[j]+=(a[j-8] case 6:f[j]+=(a[j-7] case 5:f[j]+=(a[j-6] case 4:f[j]+=(a[j-5] case 3:f[j]+=(a[j-4] case 2:f[j]+=(a[j-3] case 1:f[j]+=(a[j-2] case 0:f[j]+=(a[j-1] }/* for(;k f[j]+=(a[k] } for(unsigned int j=n,k,t,sum0,sum1,sum2,sum3,sum4,sum5,sum6,sum7;j>=2;--j){ sum0=sum1=sum2=sum3=sum4=sum5=sum6=sum7=0,k=1; if(j<7) goto ft; t=j-7; for(;k sum0+=(a[k] sum1+=(a[k+1] sum2+=(a[k+2] sum3+=(a[k+3] sum4+=(a[k+4] sum5+=(a[k+5] sum6+=(a[k+6] sum7+=(a[k+7] } ft: f[j]=sum0+sum1+sum2+sum3+sum4+sum5+sum6+sum7; switch(j-k-1){ //case 7:f[j]+=(a[j-8] case 6:f[j]+=(a[j-7] case 5:f[j]+=(a[j-6] case 4:f[j]+=(a[j-5] case 3:f[j]+=(a[j-4] case 2:f[j]+=(a[j-3] case 1:f[j]+=(a[j-2] case 0:f[j]+=(a[j-1] } } unsigned int i=2; for(;i+7<=n;i+=8){ ans0+=f[i], ans1+=f[i+1], ans2+=f[i+2], ans3+=f[i+3], ans4+=f[i+4], ans5+=f[i+5], ans6+=f[i+6], ans7+=f[i+7]; } switch(n-i){ case 6:ans+=f[n-6]; case 5:ans+=f[n-5]; case 4:ans+=f[n-4]; case 3:ans+=f[n-3]; case 2:ans+=f[n-2]; case 1:ans+=f[n-1]; case 0:ans+=f[n]; }/* for(;i<=n;++i) ans+=f[i];*/ write(ans+ans0+ans1+ans2+ans3+ans4+ans5+ans6+ans7); return 0; } 使用 C++ 14(GCC 9) 提交 90 分，#11 TLE 1.06 秒；换成 C++ 20 直接 AC，而且 #11 107 毫秒。 此内容可以稳定复现，请勿当作打回理由。 十二、OI 禁止 请勿滥用这些内容！ 编译手动优化； 命令行优化。 十三、经典题目 P3987 我永远喜欢珂朵莉~，需要使用：位运算、评测点分治（除数为 2）、循环展开、读入优化、三目运算符。 P4604 [WC2017] 挑战，需要使用：循环展开、位运算、Cache、压位、指针运算。这个是我写的题解。 Ynoi 系列题目，如果数据结构非常优秀，是正解的话通常需要卡常，但是不是专门卡常的题，其中 P3987 是其中一道题的弱化版，可以暴力卡常。 不是很经典，但是也可以卡常的题： P8796 [蓝桥杯 2022 国 AC] 替换字符，这个比较难卡，建议尝试。 上面那个题是用到冷热代码的，欢迎读者尝试。