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

作者: wjyyy 分类: 学习笔记,语言 发布时间: 2019-04-28 22:01

点击量:73

〇、前言

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

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

参考资料

一、读入数据的函数

注意,以下测试均在 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;
}

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Cesare Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
Cesare
游客

orz

/* */