为何需要快读

如果是c++党，在平时常用的输入输出应该是cin/cout，但c++为了保证cin/cout与c语言的scanf/printf可混合使用，输入流会时刻与输入缓冲保持同步，导致调用缓存，消耗过大，因此在数据量大的情况下，cin/cout的耗时缺点会被明显放大。而信竞的题目大多都是要求1s或2s过题，如此短的时间并不能被耗费在输入输出，因此就诞生了快读快写。
输入导致的超时

数据准备

由于比赛中输出一般规模较小,本文只讨论输入如何加速，我们先用代码生成1000000个随机数，构成1000*1000的矩阵，然后输入比较时间（Win 10系统）

#include <bits/stdc++.h>
using namespace std; 

int main()
{
    srand((unsigned)time(NULL));
    freopen("out1.txt","w",stdout);
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            cout<<rand()<<' ';
        }
        cout<<endl;
    }
    return 0;
}

cin的效率

在比赛中，经常出现数据集超大造成使用cin时TLE的情况，这时候大部分人（包括原来我也是）认为这是cin的效率不及scanf的错。但准确的说，cin是在不优化的情况下效率很低，我们首先用刚刚生成的数据来测试一下未优化的cin。

// 未优化的cin
#include<iostream>
#include<cstdio>
#include<ctime>
using namespace std;
int a[1005][1005];
int main()
{
    freopen("out1.txt","r",stdin);
    double s=clock();
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            cin>>a[i][j];
        }
    }
    printf("time used=%.3fs\n",double(clock()-s)/CLOCKS_PER_SEC);
    return 0;
}

可以看到，未优化过的cin在输入1000000个数字时，耗时就到了0.702s（不同的随机数据可能测试不一样）。假如运行时间限制为1s,那么程序只剩下0.3秒来计算，万一算法再写的复杂一点，是极容易导致TLE的，因此遇到大数据的情况下尽量避免用cin。
未优化的cin

早期在我还不会用scanf/printf时，我也曾找过cin/cout的优化方式。网上博客提到：默认的时候，cin与stdin总是保持同步的，也就是说这两种方法可以混用，而不必担心文件指针混乱，同时cout和stdout也一样，两者混用不会输出顺序错乱。正因为这个兼容性的特性，导致cin有许多额外的开销，如何禁用这个特性呢？只需一个语句 std::ios::sync_with_stdio(false); ，这样就可以取消cin与stdin的同步了。

另一种等价的写法
cin.tie(0);//取消cin的同步
cout.tie(0);//取消cout的同步

// 优化的cin
#include<iostream>
#include<cstdio>
#include<ctime>
using namespace std;
int a[1005][1005];
int main()
{
    freopen("out1.txt","r",stdin);
    std::ios::sync_with_stdio(false);//优化
    double s=clock();
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            cin>>a[i][j];
        }
    }
    printf("time used=%.3fs\n",double(clock()-s)/CLOCKS_PER_SEC);
    return 0;
}

可以看到时间变成了0.156s，相比未优化的cin是飞跃性的优化。不过现在个人建议不要用这种方式，因为这是取消了流与缓冲的同步实现的加速，如果此时混搭着用cin/cout和scanf/printf，很可能会导致输入输出混乱。而且据说这玩意在在NOIP的评测机上这样子会爆0，NOIP明确要求使用freopen，而freopen在stdio库中，取消了iostream和stdio的同步,会造成文件指针混乱,进而导致RE。
优化的cin

scanf的效率

既然NOIP比赛中坚决不要写std::ios::sync_with_stdio(false)，ACM比赛也最好避免去除同步导致出现玄学bug，那么我们可以用c语言的scanf/printf。

// scanf效率
#include<iostream>
#include<cstdio>
#include<ctime>
using namespace std;
int a[1005][1005];
int main()
{
    freopen("out1.txt","r",stdin);
    double s=clock();
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            scanf("%d",&a[i][j]);
        }
    }
    printf("time used=%.3fs\n",double(clock()-s)/CLOCKS_PER_SEC);
    return 0;
}

可以看到比起未优化的cin，scanf的效率提升是显著的，虽然赶不上取消同步的cin/cout，但是已经足以面对几乎所有的题目了。我本人没见过连scanf都卡掉的题，可能是我刷题还不够。
scanf的效率

手写快读的效率

根据网上的资料了解，getchar()的速度是很快的，但它只能读取单个字符，因此最简单的快读思路就是使用getchar()读取字符，然后将字符转为整型来优化读取整数的速度，同理可以转成long long。下面的代码是最简单的一种手写快读的方式，可以读任意整数。

// 快读的实现
#include<iostream>
#include<cstdio>
#include<ctime>
using namespace std;
int a[1005][1005];
// 快速读入函数
inline int read()
{
    int x=0,sign=1;
    char c=getchar();
    // 判断符号
    while(c>'9'||c<'0'){
        if(c=='-') sign=-1;
        c=getchar();
    }
    // 转换数
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*sign;
}

int main()
{
    freopen("out1.txt","r",stdin);
    double s=clock();
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            a[i][j]=read();
        }
    }
    printf("time used=%.3fs\n",double(clock()-s)/CLOCKS_PER_SEC);
    return 0;
}

可以看到，这种手写快读的效率极佳，而且不会在评测机上出现问题，也没有调用许多函数，遇到数据量大的题，我们完全可以尽量用手写的快速读入来读取。
手写快读的效率

当然，这种快速读入也可以用位运算继续优化，写法如下：

// 快速读入 
inline int read()
{
    register int x=0;register char c=getchar(),f=1;
    for(;c<48||c>57;c=getchar())if(c==45)f=-1;
    for(;c>47&&c<58;c=getchar())x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
// 快速读入(直接赋值) 
inline int read(register int &x)
{
    x=0;register char c=getchar(),f=1; // 直接赋值版，x无需重新声明，直接用传入的参数
    for(;c<48||c>57;c=getchar())if(c==45)f=-1;
    for(;c>47&&c<58;c=getchar())x=(x<<3)+(x<<1)+(c^48);
    x*=f;
}

// x=(x<<3)+(x<<1)+(c^48); x=x*10+(c^48); x=x*10+(c-48);
// 三者是等效的，用位运算("<<",">>","^","|","&","~")可以加快速度，提高效率

可以看到时间仅用0.147s，效率极佳。
快读位运算版

文件输入输出版

如果还不满足速读/写的速度怎么办？还有更快的文件(fread、fwrite)版。fread/fwrite是一种比getchar/putchar还快的输入输出函数，他涉及文件流、指针等知识（fread_百科）。文件方式暂时没有负数版本。

// fread读入
#define getc() (_b1==_b2?fread(_b,1,100000,stdin),_b2=_b+100000,*((_b1=_b)++):*(_b1++))
char _b[100000],*_b1,*_b2;
inline void read(register int &x)
{
    x=0;register char c=getc();
    for(;c<48||c>57;c=getc());
    for(;c>47&&c<58;c=getc())x=(x<<3)+(x<<1)+(c^48);
}

1000000级别的数据量，读入时间立即缩短到只有0.016s，几乎等于没有耗时。
fread()的效率

总结

  1. 遇到大数据时尽量避免用cin
  2. NOIP比赛中坚决不要写std::ios::sync_with_stdio(false)来优化cin
  3. 如果是double或输入输出格式较复杂的题，直接用scanf/printf
  4. 遇到数据量大的题，且是long long或int，尽量用手写的快速读入来读取

个人建议

大多数的信竞题并不会卡输入输出，但是有些时候会遇到一些输入输出数据量比较大的题目，如果此时我们还用cin和cout，很有可能就获得多发TLE。我与队友曾经在多校训练时就被这种毒瘤错误卡过题，当时我们看着代码对核心算法左改右改，却一直TLE，最后某个队友自暴自弃的把所有cin/cout改成了scanf/printf，然后就过了。说实话这种非算法性的错误，往往最容易让人钻牛角尖（另一种就是数据范围边界值特判），最后搞崩人的心态，在这种地方wa掉着实可惜，因此我个人建议输入输出还是要熟练运用scanf/printf，以及至少一种手写快读快写的方法。
大佬的ACM & 我的ACM

参考资料

版权属于：PCsky

本文链接：http://www.hyouka.club/index.php/archives/92/

转载时须注明出处及本声明

最后修改：2022 年 06 月 15 日 05 : 21 PM
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏