浅谈卡常（未完待续）

linxuanrui · 2024-05-19 15:57:14 · 算法·理论

1.什么是卡常？为什么要卡常？

卡常数，又称底层常数优化，是信息学竞赛中一种针对程序基本操作进行空间或时间上优化的行为，与时间复杂度或剪枝有别。

在 OI 竞赛中，经常会出现没办法写出正解的情况。通常，我们会选择打暴力。打暴力只能获得一部分的分数，因为时间复杂度不对。

卡常就可以让程序常数变少，可能可以得到更多的分数。甚至让暴力 AC 题目，达到“暴力碾标算”的境界。

这篇文章将会由浅入繁的介绍一些卡常的技巧。本文较长，还请耐心阅读。

由于作者水平不足，文章中可能会出现疏漏及错误，欢迎指出。

2.输入输出优化

这里主要讲四种输入输出优化的方法：

1. cin/cout + 关闭同步流。
2. scanf/printf。
3. 快读快写。
4. fread/fwrite。

2.1.cin/cout+关闭同步流

首先，我们得了解 cin/cout 的原理。

cin/cout 是利用了缓冲区。每次输入或输出程序就会刷新缓冲区，把缓冲区里的内容读入或输出到控制台中。

但是，刷新缓冲区是需要时间的。大量的刷新缓冲区可能会导致程序效率变低，甚至导致超时。

关闭同步流就是可以解决上述问题的方法。关闭同步流的代码如下：

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

但是，关闭同步流也不是没有弊端的。用了关闭同步流之后，C 与 C++ 的输入、输出就不能连用了。

2.2.scanf/printf

scanf/printf 是 C 语言的输入输出，而 C 语言会比 C++ 快一些，所以 scanf/printf 天生就比普通的 cin/cout 快。

scanf/printf 不但效率上优于普通的 cin/cout 快，而且面对特殊的输入或输出格式下，还比 cin/cout 方便。

比如读入 11:45 这个时间，并输出时和分。

cin/cout：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
string s;
signed main(){
    cin >> s;
    int pos = s.find(":");
    int a = atoll(s.substr(0,pos).c_str()),b = atoll(s.substr(pos + 1).c_str());
    cout << a << " " << b;
}

csanf/printf：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
int a,b;
signed main(){
    scanf("%d:%d",&a,&b);
    printf("%d %d",a,b);
}

2.3.快读快写

众所周知，在 C++ 中有两个函数 getchar() 和 putchar()，它们分别是用来读入和输出一个字符，效率也十分的快。

因此，我们可以考虑将一个数字看成是由数字字符组成的字符串，然后逐字符读入即可。

输出也差不多。直接一个一个数位输出即可。

int read(){
    int t = 1,x = 0;char ch = getchar();
    while(!isdigit(ch)){if(ch == '-')t = -1;ch = getchar();}
    while(isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
    return t * x;
}
void write(int x){
    if(x < 0)x = -x,putchar('-');
    if(x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}

2.4.fread/fwrite

游戏最后的怪兽一般都是 boss，fread/fwrite 正是输入输出的大 boss。

在使用 fread 和 fwrite 之前，请提前测试一下你的电脑支不支持，测试代码：

#include <bits/stdc++.h>
using namespace std;
char buf[10];
int main() {
    fread(buf,1,sizeof(buf),stdin);
    cout << ferror(stdin) << endl;
    return 0;
}

编译（请使用 C++11）并运行后，输入 123456 + 回车 + Ctrl+Z + 回车。如果输出不是 0。那就说明您的电脑可能不太适合使用 fread（其实就是后果自负的意思）。

fread 和 fwrite 的定义分别如下：

size_t fread(void* buffer, size_t size, size_t count,FILE* stream);

size_t fwrite(const void* buffer, size_t size, size_t count, FILE* stream);

fread 其实就是从给定输入流 stream 读取最多 count 个对象到数组 buffer 中，把 buffer 当作 unsigned char 数组并顺序保存结果。流的文件位置指示器前进读取的字节数。

fwrite 也差不多。

如果你仔细阅读 fread 的定义的话，你就会发现，fread 其实就是把 buffer 当成缓冲区，从流 stream 中读取 count 个数据。

能优化的原因也类似 cin/cout + 关闭同步流。

利用 fread 和 fwrite，我们可以改进快读快写中的 getchar() 和 putchar()。

改进后的代码：

namespace fastIO{
    #define f_inline inline __attribute__((always_inline))
    //上面是一些神秘的优化，待会会讲
    char buf[3145728],*p1 = buf,*p2 = buf;//3145728 byte = 3 MB
    f_inline char gc(){return (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,3145728,stdin),p1 == p2) ? EOF : *p1++);}
    //getchar() 改进：
    //如果已经将缓冲区读到末尾了（也就是 p1 == p2），然后就用 fread 再读一次
    //如果再次 fread 之后还是将缓冲区读到末尾了，那么返回 EOF
    //否则返回缓冲区的下一个字符
    template <typename T>f_inline T read(){//读入一个数字 
        register T x = 0,f = 1;char ch = gc();
        while(!isdigit(ch)){if(ch == '-')f = -1;ch = gc();}
        while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48),ch = gc();}
        return f * x; 
    }
    char buffer[1048576];int _p1 = -1;const int _p2 = 1048575;//1048576 byte = 1MB
    f_inline void flush(){fwrite(buffer,1,_p1 + 1,stdout),_p1 = -1;}
    //刷新缓冲区
    f_inline void putchar(const register char &x){if(_p1 == _p2)flush();buffer[++_p1] = x;}
    //putchar() 改进：
    //如果缓冲区满了，那么刷新缓冲区
    //否则，把字符输出到缓冲区中
    template <typename T>inline void write(T x){//输出一个数字 
        if(x < 0){putchar('-'),x = -x;}
        const register T tmp = x / 10;
        if(x > 9)write(tmp);
        putchar(x - (tmp << 1) - (tmp << 3) ^ 48);
    }
};
//调用方法：
//x = read<int>();
//write<int>(x);

注意，当程序结束后需要刷新一次缓冲区，也就是调用一次 flush()。

注意：并不是 buf 和 buffer 数组的大小越大越好，在第 7 章会解释。

2.5.效率比较

该测试将在 Windows 和 Linux 系统下进行。

Windows 是 Windows 11，版本 23H2（OS 内部版本 22635.2700）。编译选项是 -std=c++14 -static -Wall -Wextra -Wl,-stack=536870912 -O2。

Linux 用的是 Hydro 的评测机。

首先，这是用来生成输入的代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
const int N = 300;
int a[10] = {1,1,10,100,1000,10000};
signed main(){
    mt19937_64 rand(time(0));
    for(int i = 1;i <= 5;i++){
        string file = "test" + to_string(i) + ".in";
        freopen(file.c_str(),"w",stdout);
        cout << N * a[i] << endl;
        for(int j = 1;j <= N * a[i];j++)cout << rand() << " ";
        fclose(stdout);
    }
}

这段代码会生成 5 个文件，分别是 test1.in ~ test5.in。数据有梯度，第 i 个文件会有 3\times10^{i+1} 个数。

生成的 5 个文件总共的大小是 35,805,118 字节，大约是 34 MB。

cin/cout + 关闭同步流测试代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
const int N = 3e7 + 5; 
int n,a[N];
clock_t st,en;
double sum;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("output.txt","w",stdout);
    for(int i = 1;i <= 5;i++){
        string file = "test" + to_string(i) + ".in";
        ifstream cin(file.c_str());
        st = clock();
        cin >> n;
        for(int j = 1;j <= n;j++)cin >> a[j];
        for(int j = 1;j <= n;j++)cout << a[j] << " ";
        en = clock();
        double tmp = (double)(en - st) / CLOCKS_PER_SEC;
        sum += tmp;
        cerr << "#" << i << " cin/cout used time: " << fixed << setprecision(5) << tmp << "s.\n";
    }
    cerr << "\nAll: cin/cout used time: " << fixed << setprecision(5) << sum << "s.\n"; 
    cerr << "Average: cin/cout used time: " << fixed << setprecision(5) << sum / 5 << "s."; 
}

测试结果（Windows）：

#1 cin/cout used time: 0.00000s.
#2 cin/cout used time: 0.00000s.
#3 cin/cout used time: 0.02400s.
#4 cin/cout used time: 0.17300s.
#5 cin/cout used time: 1.57100s.

All: cin/cout used time: 1.76800s.
Average: cin/cout used time: 0.35360s.

Linux：

总用时：597ms；平均用时：119ms。

scanf/printf 代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
const int N = 3e7 + 5; 
int n,a[N];
clock_t st,en;
double sum;
signed main(){
    freopen("output.txt","w",stdout);
    for(int i = 1;i <= 5;i++){
        string file = "test" + to_string(i) + ".in";
        freopen(file.c_str(),"r",stdin);
        st = clock();
        scanf("%lld",&n);
        for(int j = 1;j <= n;j++)scanf("%lld",&a[j]);
        for(int j = 1;j <= n;j++)printf("%lld ",a[j]);
        en = clock();
        double tmp = (double)(en - st) / CLOCKS_PER_SEC;
        sum += tmp;
        cerr << "#" << i << " scanf/printf used time: " << fixed << setprecision(5) << tmp << "s.\n";
    }
    cerr << "\nAll: scanf/printf used time: " << fixed << setprecision(5) << sum << "s.\n"; 
    cerr << "Average: scanf/printf used time: " << fixed << setprecision(5) << sum / 5 << "s."; 
}

测试结果（Windows）：

#1 scanf/printf used time: 0.00000s.
#2 scanf/printf used time: 0.00900s.
#3 scanf/printf used time: 0.08200s.
#4 scanf/printf used time: 0.69100s.
#5 scanf/printf used time: 7.05500s.

All: scanf/printf used time: 7.83700s.
Average: scanf/printf used time: 1.56740s.

Linux：

总用时：790ms；平均用时：158ms。

快读快写代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
const int N = 3e7 + 5; 
int n,a[N];
clock_t st,en;
double sum;
int read(){
    int t = 1,x = 0;char ch = getchar();
    while(!isdigit(ch)){if(ch == '-')t = -1;ch = getchar();}
    while(isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
    return t * x;
}
void write(int x){
    if(x < 0)x = -x,putchar('-');
    if(x > 9)write(x / 10);
    putchar(x % 10 ^ 48);
}
signed main(){
    freopen("output.txt","w",stdout);
    for(int i = 1;i <= 5;i++){
        string file = "test" + to_string(i) + ".in";
        freopen(file.c_str(),"r",stdin);
        st = clock();
        n = read();
        for(int j = 1;j <= n;j++)a[j] = read();
        for(int j = 1;j <= n;j++)write(a[j]),putchar(' ');
        en = clock();
        double tmp = (double)(en - st) / CLOCKS_PER_SEC;
        sum += tmp;
        cerr << "#" << i << " fast read/write used time: " << fixed << setprecision(5) << tmp << "s.\n";
    }
    cerr << "\nAll: fast read/write used time: " << fixed << setprecision(5) << sum << "s.\n"; 
    cerr << "Average: fast read/write used time: " << fixed << setprecision(5) << sum / 5 << "s."; 
}

Linux：

测试结果（Windows）：

#1 fast read/write used time: 0.00000s.
#2 fast read/write used time: 0.00000s.
#3 fast read/write used time: 0.02400s.
#4 fast read/write used time: 0.21000s.
#5 fast read/write used time: 2.18400s.

All: fast read/write used time: 2.41800s.
Average: fast read/write used time: 0.48360s.

总用时：472ms；平均用时：94ms。

fread/fwrite 代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
const int N = 3e7 + 5; 
int n,a[N];
clock_t st,en;
double sum;
namespace fastIO{
    #define f_inline inline __attribute__((always_inline))
    char buf[1 << 21],*p1 = buf,*p2 = buf;
    f_inline char gc(){return (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1 << 21,stdin),p1 == p2) ? EOF : *p1++);}
    f_inline int read(){//读入一个数字 
        register int x = 0,f = 1;char ch = gc();
        while(!isdigit(ch)){if(ch == '-')f = -1;ch = gc();}
        while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48),ch = gc();}
        return f * x; 
    }
    char buffer[1 << 21];int _p1 = -1;const int _p2 = 1 << 21 - 1;
    f_inline void flush(){fwrite(buffer,1,_p1 + 1,stdout),_p1 = -1;}
    f_inline void putchar(const register char &x){if(_p1 == _p2)flush();buffer[++_p1] = x;}
    inline void write(int x){//输出一个数字 
        if(x < 0){putchar('-'),x = -x;}
        int tmp = x / 10;
        if(x > 9)write(tmp);
        putchar(x - (tmp << 1) - (tmp << 3) ^ 48);
    }
};
using namespace fastIO;
signed main(){
    freopen("output.txt","w",stdout);
    for(int i = 1;i <= 5;i++){
        string file = "test" + to_string(i) + ".in";
        freopen(file.c_str(),"r",stdin);
        st = clock();
        n = read();
        for(int j = 1;j <= n;j++)a[j] = read();
        for(int j = 1;j <= n;j++)write(a[j]),fastIO::putchar(' ');
        flush();
        en = clock();
        tmp += (double)(en - st) / CLOCKS_PER_SEC;
        sum += tmp;
        cerr << "#" << i << " fread/fwrite used time: " << fixed << setprecision(5) << tmp << "s.\n";
    }
    cerr << "\nAll: fread/fwrite used time: " << fixed << setprecision(5) << sum << "s.\n"; 
    cerr << "Average: fread/fwrite used time: " << fixed << setprecision(5) << sum / 5 << "s."; 
}

测试结果（Windows）：

#1 fread/fwrite used time: 0.00100s.
#2 fread/fwrite used time: 0.00100s.
#3 fread/fwrite used time: 0.00800s.
#4 fread/fwrite used time: 0.04000s.
#5 fread/fwrite used time: 0.36400s.

All: fread/fwrite used time: 0.41400s.
Average: fread/fwrite used time: 0.08280s.

Linux：

总用时 276ms；平均用时 53ms。

3.STL的优化

STL，即为 Standard Template Library，标准模板库。STL 的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。

STL 带给了我们很大的便利，但是与之付出的代价就是时间的变慢。当然，开启 O2 可以解决大部分的问题。

解决 STL 太慢的方法只有一种——手写。具体可以参考第 5 章中的手写 bitset。

这里提供常见 STL 的底层机制。

4.选择合适的类型

提起这个，我就想起有一次我用了 long long，100pts -> 50pts。

在 C++ 中，由于存储方式、大小的不同，效率也会有所不同。

这里拿 int 举例。

11011101 00001100 10100001 00011101 这就是 int 在 C++ 的存储方式。

每 8 位是一个字节。第一位是符号位，剩余 31 位表示二进制下的数。

比较效率的程序代码：

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
template<typename T>
void testInt(string type){
    clock_t st,en;
    T x = 2;
    st = clock();
    for(int i = 1;i <= 200000000;i++)x = x * x - 6 + (x / (x - !x));
    en = clock();
    cout << type << " used time: " << (double)(en - st) / CLOCKS_PER_SEC << "s." << endl;
}
template<typename T>
void testDouble(string type){
    clock_t st,en;
    T x = 11.4514;
    st = clock();
    for(int i = 1;i <= 200000000;i++)x = x * x / 3 + (x / (x - !x));
    en = clock();
    cout << type << " used time: " << (double)(en - st) / CLOCKS_PER_SEC << "s." << endl;
}
template<typename T>
void testOther(string type){
    clock_t st,en;
    T x = 1;
    st = clock();
    for(int i = 1;i <= 200000000;i++)x = ((!x) & x) ^ ((~x) | x) << x;
    en = clock();
    cout << type << " used time: " << (double)(en - st) / CLOCKS_PER_SEC << "s." << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
    testOther<bool>("bool");
    testInt<char>("char");
    testInt<unsigned char>("unsigned char");
    testInt<short>("short");
    testInt<unsigned short>("unsigned short");
    testInt<int>("int");
    testInt<unsigned int>("unsigned int");
    testInt<long>("long");
    testInt<unsigned long>("unsigned long");
    testInt<long long>("long long");
    testInt<unsigned long long>("unsigned long long");
    testDouble<float>("float");
    testDouble<double>("double");
    testDouble<long double>("long double");
}

测试结果：

bool used time: 0.349s.
char used time: 1.755s.
unsigned char used time: 1.539s.
short used time: 1.941s.
unsigned short used time: 1.945s.
int used time: 1.454s.
unsigned int used time: 1.61s.
long used time: 1.5s.
unsigned long used time: 1.574s.
long long used time: 1.836s.
unsigned long long used time: 2.325s.
float used time: 2.41s.
double used time: 2.695s.
long double used time: 239.015s.

bool 测试用的是位运算，因此会快很多。至于应用吗，待会再讲（

在整形变量（包括 char）中，最快的是 int，这一点是母庸置疑的。

在浮点型变量中，最快的是 float，不过 long double 慢的有点离谱了。

5.二进制压位

如果把上面的代码稍微改一下，变成这样：

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
template<typename T>
void test(string type){
    clock_t st,en;
    T x = 1;
    st = clock();
    for(int i = 1;i <= 200000000;i++)x = ((!x) & x) ^ ((~x) | x) << x;
    en = clock();
    cout << type << " used time: " << (double)(en - st) / CLOCKS_PER_SEC << "s." << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
    test<bool>("bool");
    test<short>("short");
    test<unsigned short>("unsigned short");
    test<int>("int");
    test<unsigned int>("unsigned int");
    test<long>("long");
    test<unsigned long>("unsigned long");
    test<long long>("long long");
    test<unsigned long long>("unsigned long long");
}

这样，运行的结果就会变成：

bool used time: 0.354s.
short used time: 0.717s.
unsigned short used time: 0.681s.
int used time: 0.175s.
unsigned int used time: 0.185s.
long used time: 0.184s.
unsigned long used time: 0.191s.
long long used time: 0.329s.
unsigned long long used time: 0.335s.

这时，你可能就会有疑问了：为什么 bool 类型速度这么慢，几乎不敌所有数据类型？

上一章谈到，计算机中使用二进制位来存储数据的。

而 bool 存储在计算机中，浪费了很多字节，因此才会慢。（待考证）

因此，有一种想法就是：利用位运算运行极快的性质，将多个 bit 压成一个 unsigned long long 的数。（只要是 unsigned 就可以）

不过，万能的 STL 还是帮我们实现了二进制压位。就是 bitset。

bitset 会将每八个 bit 压成一个 byte。这样，就实现了时间、空间常数的同时除以 8。

根据这个原理，我们也可以将每八个 bit 压成一个 unsigned long long。这里测试一下效率。

数据生成器：

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
uniform_int_distribution<int> dis1(0,1);
uniform_int_distribution<int> dis2(1,3);
uniform_int_distribution<int> dis3(1,10000);
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("a.txt","w",stdout);
    mt19937_64 rand(time(0));
    int n = 10000,q = 10000;
    cout << n << " " << q << endl;
    while(n--)cout << dis1(rand) << " ";
    while(q--){
        cout << dis2(rand) << " " << dis3(rand) << endl;
    }
}

手写：

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
const int SIZE = 1e6 + 5;
struct Bitset{
    unsigned long long b[SIZE];
    void set(){memset(b,0xff,sizeof(b));}
    void set(int pos){b[pos >> 6] |= (1ull << pos);}
    void reset(){memset(b,0,sizeof(b));}
    void reset(int pos){b[pos >> 6] &= ~(1ull << pos);}
    bool test(int pos){return (b[pos >> 6] & (1ull << pos));}
}b;
int n,q,opt,x;
double sum;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("a.txt","w",stdout);
    clock_t st,en;
    st = clock();
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        cin >> x;
        if(x == 1)b.set(x);
    }
    while(q--){
        cin >> opt >> x;
        if(opt == 1)b.set(x);
        else if(opt == 2)b.reset(x);
        else cout << b.test(x) << endl;
    }
    en = clock();
    sum += (en - st);
    cout << fixed << setprecision(5) << (en - st) * 1.00 / CLOCKS_PER_SEC << "s" << endl;
}

输出：0.05200s。

STL bitset：

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
const int SIZE = 1e6 + 5;
bitset<SIZE> b;
int n,q,opt,x;
double sum;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("a.txt","r",stdin);
    clock_t st,en;
    st = clock();
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        cin >> x;
        if(x == 1)b.set(x);
    }
    while(q--){
        cin >> opt >> x;
        if(opt == 1)b.set(x);
        else if(opt == 2)b.reset(x);
        else cout << b.test(x) << endl;
    }
    en = clock();
    sum += (en - st);
    cout << fixed << setprecision(5) << (en - st) * 1.00 / CLOCKS_PER_SEC << "s" << endl;
}

输出：0.06900s。

6.取模优化

众所周知，C++ 的取模速度比较慢，有着较大的常数。但是，有时候将模数改为常量^{[1]}就会有较大的速度提升。这是为什么呢？

这用到了一个叫做“barrett 约减”的方法。barrett 约减的原理是用成本较低的乘法、位运算代替取模（整除）。

这里由于作者水平有限（如果搞懂了的话，作者可能会补充），只给出链接参考：[barrete约减_巴特雷特约减-CSDN博客](https://blog.csdn.net/weixin_39057744/article/details/127265345?ops_request_misc=%7B%22request%5Fid%22%3A%22170082114416800213053730%22%2C%22scm%22%3A%2220140713.130102334.pc%5Fall.%22%7D&request_id=170082114416800213053730&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-5-127265345-null-null.142^v96^pc_search_result_base3&utm_term=barrett 约减&spm=1018.2226.3001.4187)。