卡常

DuskDawn · 2022-10-05 20:28:47 · 个人记录

\texttt{Faster!Faster!!Faster!!!}

怎样更快？

当你面对残酷的 \texttt{TLE} 却又不愿意承认自己的算法有问题时，卡常是一个很好的办法。

卡常又称卡常数、底层常数优化，是 \texttt{OI} 中一种针对程序基本操作进行空间或时间上优化的行为。

卡常第壹式——快读 & 快写

众所周知，字符输入输出比标准输入输出快得多。

快读和快写就是运用了这个原理。

快读模板：

template <typename T>
void read(T &x) {
    x=0;
    int f=1;
    char ch=getchar();
    while (!isdigit(ch)){
        if (ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    x*=f;
}

用法：

read(n);//输入并赋值

快写模板：

template <typename T>
void write(T x) {
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(x>9) {
        write(x/10);
    }
    putchar(x%10+'0');
}

用法：

write(n);//输出n

卡常第贰式——位运算

位运算是直接对数据在内存中的二进制数进行运算，速度自然比四则运算要快，能用就用。

不懂位运算的的看这里。

乘除法最好用位移代替：

2 \times 2 = 2 << 1,2 \times 10 = (2 << 1) + (2 << 3)

90 \div 2 = 90 >> 1,128 \div 16 = 128 >> 4

小知识：

&   =   bitand
|   =   bitor
^   =   xor
&=   =   and_eq
|=   =   or_eq
^=   =   xor_eq
~   =   compl

位运算的其他应用：

1.代替模运算

17 mod 2 = 17 & 1,45 mod 4 = 45 & 3,986 mod 16 = 986 & 15

2.快速幂

快速幂模板：

#include <iostream>
using namespace std;
long long b,p,k,ans=1,b1,p1;
int main(){
    cin>>b>>p>>k;
    b1=b;
    p1=p;
    while (p){//求b^p mod k
        if (p&1){//&代替取模
            ans*=b;
            ans%=k;
        }
        b*=b;
        b%=k;
        p>>=1;//>>代替除法
    }
    cout<<b1<<'^'<<p1<<" mod "<<k<<'='<<ans;
    return 0;
}

3.交换两个数的值

a^=b^=a^=b//请自行思考原理

卡常第叁式——\texttt{inline}

在函数之前加上 \texttt{inline}，会使其变成内联函数，可以加快函数调用，但只适用于简单且调用频繁的函数。涉及递归、大的循环等很复杂的函数，编译器会自动忽略 \texttt{inline}。

快读函数就可以加上 \texttt{inline}，但有时 \texttt{inline} 会被忽略。

卡常第肆式——寄存器

假设你要拿草稿纸，一个在桌子上，一个在打印机里，你拿哪一张?

就近原则。

寄存器相较于内存离 CPU 更近，所以 CPU 可以更快地访问寄存器。

从工作原理上说，寄存器的工作原理比内存简单得多。

综上，寄存器与内存存在小差异。我们可以使用寄存器来提高访问速度，往往运用于经常访问的变量。

例如：

for (register int i=1;i<=1000000000;i++)

# 卡常第伍式——三目运算符相较于 $\texttt{if-else}$，三目运算符的汇编指令更短。在少量的运行中，二者的区别微乎其微；但运行次数庞大时，三目运算符的优势便显现出来。 # 卡常第陆式——常数的声明尽量将常数声明成常量： `const int mod=1000000009;` 比 `int mod=1000000009;` 要快。 # 卡常第柒式——O2优化经常听到 $\texttt{O2}$ 这一说法，代码实现为： `#pragma GCC optimize(2)` ## 究极优化： ```cpp #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #pragma G++ optimize(1) #pragma G++ optimize(2) #pragma G++ optimize(3) #pragma G++ optimize("Ofast") #pragma G++ optimize("inline") #pragma G++ optimize("-fgcse") #pragma G++ optimize("-fgcse-lm") #pragma G++ optimize("-fipa-sra") #pragma G++ optimize("-ftree-pre") #pragma G++ optimize("-ftree-vrp") #pragma G++ optimize("-fpeephole2") #pragma G++ optimize("-ffast-math") #pragma G++ optimize("-fsched-spec") #pragma G++ optimize("unroll-loops") #pragma G++ optimize("-falign-jumps") #pragma G++ optimize("-falign-loops") #pragma G++ optimize("-falign-labels") #pragma G++ optimize("-fdevirtualize") #pragma G++ optimize("-fcaller-saves") #pragma G++ optimize("-fcrossjumping") #pragma G++ optimize("-fthread-jumps") #pragma G++ optimize("-funroll-loops") #pragma G++ optimize("-fwhole-program") #pragma G++ optimize("-freorder-blocks") #pragma G++ optimize("-fschedule-insns") #pragma G++ optimize("inline-functions") #pragma G++ optimize("-ftree-tail-merge") #pragma G++ optimize("-fschedule-insns2") #pragma G++ optimize("-fstrict-aliasing") #pragma G++ optimize("-fstrict-overflow") #pragma G++ optimize("-falign-functions") #pragma G++ optimize("-fcse-skip-blocks") #pragma G++ optimize("-fcse-follow-jumps") #pragma G++ optimize("-fsched-interblock") #pragma G++ optimize("-fpartial-inlining") #pragma G++ optimize("no-stack-protector") #pragma G++ optimize("-freorder-functions") #pragma G++ optimize("-findirect-inlining") #pragma G++ optimize("-frerun-cse-after-loop") #pragma G++ optimize("inline-small-functions") #pragma G++ optimize("-finline-small-functions") #pragma G++ optimize("-ftree-switch-conversion") #pragma G++ optimize("-foptimize-sibling-calls") #pragma G++ optimize("-fexpensive-optimizations") #pragma G++ optimize("-funsafe-loop-optimizations") #pragma G++ optimize("inline-functions-called-once") #pragma G++ optimize("-fdelete-null-pointer-checks") ``` 快到飞起~~~ ## 注意！！ - **该优化仅适用于 $\texttt{C++}$，其他语言（包括 $\texttt{C}$）可能会出现编译错误或负优化**。 - **上述优化在比赛、考试中禁用（你谷也不能用），仅适合日常骗分。** # 卡常第捌式——其他卡常 1. 后置 ++ 需要保存临时变量以返回之前的值，在 STL 中非常慢。事实上，$\texttt{int}$ 的后置 ++ 在实测中也比前置 ++ 慢 0.5 倍左右。 1. 逗号比分号快。 1. $\texttt{bool}$ 很慢，尽量开 $\texttt{int}$（但是 $\texttt{bool}$ 比 $\texttt{int}$ 省空间）。一些卡常在正规比赛中**禁用**。 **可以发现，卡常都是一些看着不起眼的优化，但它们确实对提高程序效率起到了至关重要的作用。** >行了，你已经是世界上最快的~~男人~~OIer了。 by [hear](https://blog.csdn.net/sight_720/article/details/122919247)