fread 相关快速读入 学习笔记【语言】

点击量：430

〇、前言

之前在浙江集训的时候，有一道 $n\le 3\times 10^6$ 的题，解题复杂度是 $O(n\alpha(n))$ 的，但是我丑得要命的大概是 $O(n\log n)$ 的 read() 被卡掉了。_(:з」∠)_

后来用了 fread() 的黑科技就过了，从此下定决心要学更厉害的快读。

参考资料

• 洛谷日报#110 浅谈C++ IO优化——读优输优方法集锦 by encore

一、读入数据的函数

注意，以下测试均在 C++11 且无 -O2 环境下完成。

1.scanf()

C 语言中最常用的也是最简单的读入函数，可以读入多种类型。但一般在快速读入中我们不会用到。

在我的计算机上，使用 scanf("%c",&s);，一秒可以读入 $7\times 10^6$ 以上个字符。

2.std::cin

C++ 中最好用的读入函数，通过流可以读入多种类型，并且不需要控制格式。

在我的计算机上，使用 std::cin>>s;，一秒可以读入 $4.5\times 10^6$ 以上个字符。

在加入 std::ios::sync_with_stdio(false); 后可以关闭流同步，会比 scanf 快，但是对 <cstdio> 库有影响，要慎用。

加入该命令后，在我的计算机上，使用 std::cin>>s，一秒可以读入 $9\times 10^7$ 以上个字符。

3.getchar()

每次读入单独一个字符，经常会被应用到快速读入中去。

在我的计算机上，使用 s=getchar()，一秒可以读入 $2\times 10^7$ 以上个字符。

4.gets()

每次读入一整行，一般会被运用到一些毒瘤字符串题中。

虽然它和读单个字符的关系并不是很大，我依然对它进行了测试。

在我的计算机上，使用 gets(s);，一秒可以读入 $2\times 10^7$ 以上行单个字符。

5.fread()

fread() 有四个参数，第一个是即将写入的地址，第二个是地址所代表类型的字节大小，第三个是读入的元素个数，第四个是文件指针。

假设我们现在调用 fread(s,1,10,stdin);，说明我们从标准输入中读入 $10$ 个字符放到字符数组 s[] 中去。

在我的计算机上，使用 fread(s,1,100000,stdin);，$\bf 0.1$ 秒可以读入 $500$ 以上次，约合 $5\times 10^7$ 个字符。

当然，上述一切测试都有偶然性且不专业。只是为了比较各种读入方式的大体效率差别。

二、普通读入优化

也就是前面说的被卡掉了的优化2333

使用 getchar()，可以比 scanf() 更快。我们从前往后读入一个数字，那么越早读入的字符的数位就越高。那么当读入一个新的数位时，比他高的数位就要集体 $\times 10$。

int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+(ch&15);
        ch=getchar();
    }
    return x*f;
}

注意要判断负数。其中的 ch&15 等价于 ch-'0'，可以通过研究 ASCII 码来理解。

三、基于 fread() 的读入优化

fread() 可以提前用很快的速度把很多字符存在一个字符数组里面，这样每次取一个字符返回给 gc()。当数组里面的字符用完了，再重新读入一遍。

局限：只能使用文件读入。

简化版：

#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;

它可以用一行三目运算符完成所有工作。

我们展开它来分析：

详细版：

char buf[1<<21],*p1=buf,*p2=buf;
char gc()
{
    if(p1!=p2)
        return *p1++;
    p1=buf;
    p2=p1+fread(buf,1,1<<21,stdin);
    return p1==p2?EOF:*p1++;
}

fread() 的返回值是 int。

首先，如果文件在 $2^{21}$ 个字符后没有结束，则 fread 会返回 $2^{21}$；否则会返回读入的字符个数。

当 $p1$ 没有读完字符数组时，直接返回 $p1$，并把它转到它后面的一个就可以了；如果读完了或者文件结束了，即 $p1=p2$，就返回 EOF。

然后把 gc() 当 getchar() 在原来的快读里用就好了。

当然如果要交到 OJ 上，文件问题可以用一个 define 解决，如

#ifdef wjyyy
    freopen("a.in","r",stdin);
#endif

只需要在编译命令里加上 -Dwjyyy 就可以了。

四、A+B Problem

#include<cstdio>
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int read()
{
    int x=0,f=1;
    char ch=gc();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=gc();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+(ch&15);
        ch=gc();
    }
    return x*f;
}
int main()
{
    #ifdef wjyyy
        freopen("a.in","r",stdin);
    #endif
    int a=read();
    int b=read();
    printf("%d\n",a+b);
    return 0;
}