快读攻略（详）

学委 · 2018-11-01 11:13:19 · 个人记录

读入、输出的时间也吃运行耗时。快读可以给算法部分节省时间，帮助暴力，或者占时间优势冲刺 rank1！

快读大概有多快……

某 NOIlinux 测试，多于两千组，clock() 计时的，不加优化。

读入整数包括读取字符和计算、赋值给变量，因此 fread 省去读入时间的比例非常高。不过，scanf 灵活性好强……

快读不好写？

普通快读的原理和实现都很普通，嗯嗯。

而它可以用 fread 优化。别慌，fread 所做的事情，也就类似于

scanf("%s", a);

普通快读

知道就不用看了

原理

“如题面无特殊说明，输入文件格式如下：除两两相邻的元素之间均有单个空格符外，文件中将不会出现其他空格；包括最后一行数据在内，文件中的每一行末尾均有一个回车。”

• 数字之间用空格或者换行符来分隔。

• 关于负数，负号后面是它的绝对值。

• 由于数字正向给出，所以要读入 146 可以这样：

  • 读入 1，记录 1。

  • 读入 4，先把之前的记录乘以 10，然后加上 4。现在记录了 14。

  • 读入 6，先把之前的记录乘以 10，然后加上 6。现在记录了 146。

  • 读到空格、换行符或者 EOF（读不到东西），就可以返回结果：146。

• 我们用 getchar() 逐个读进数字字符，再减去字符 '0'(ASCII码为 48) 即得对应的数字。

实现

后面跟着解释

#include <cstdio>
#include <cctype>
inline int getint()
{
    int res = 0, neg = 0, ch = getchar();

    while(!(isdigit(ch) or ch == '-') and ch != EOF)
        ch = getchar();

    if(ch == '-')
        neg = 1, ch = getchar();

    while(isdigit(ch))
        res = res * 10 + (ch - '0'), ch = getchar();

    return neg ? -res : res;
}

普通快读，每次读一个整数。这个函数分成五个简单的部分：

• 定义临时变量

  • 上面定义了 res 用来存数字部分；neg 标记是不是负数。

• 通过不断 getchar 来跳过间隔符，直到负号或者数字

  • 用 isdigit()（来自 <cctype>）判断 ch 是不是数字字符。循环退出的时候 ch 一定是负号或数字，或者读入失败（得到了 EOF）。

• 判断是不是遇到到负号了

  • 如果是则 neg 赋为 1，并读入下一个字符（后面一个肯定是数字）。

• 不断读入数字，累加数字部分

• 根据负号标记返回结果 res

说明

• isdigit() 不慢，分析汇编代码得出的哦。

• 最好保留特判 ch != EOF，很有用。

• 现在主要花时间在 getchar() 上了。

测试

语文成绩 2000万个两位数

HH的项链 150万个五位数

如何比这个读入更快？

begin
    read(n)
end.

用 fread 优化普通快读

就是优化 getchar()

语法

函数 fread() 在 <cstdio> 里。它能把数据读到你指定的位置。它做的只是把字符读进来……

• fread() 是一小块一小块地读入数据的。你要给它 4 个参数：

  存到哪里，“每块”包含几个字节，想要读几块，从哪里读入。

  char a[1000010];
  fread(a, 1, 1000000, stdin);
  //从stdin（标准输入）读入了1000000个字符到a数组里，每个char占一个字节
  
  //不连接文件的话stdin就是你的键盘输入
  //freopen("data.in", "r", stdin)之后当然就是从data.in里面fread了

• fread() 会返回一个数值，表示成功读入了几块。

这段代码以后字符数据都在 a 数组里了。所以 getchar 就不要了。

我们自己写一个函数来替代 getchar()。

实现

const int BUFSIZE = 1 << 20;//1048576

char tmp[BUFSIZE];
int cnt = 0, Max = 0;

inline char getch()
{
    if(cnt == Max)
    {
        cnt = 0;
        Max = fread(tmp, 1, BUFSIZE, stdin);
    }

    return tmp[cnt++];
}

• 先开了一个缓存区，因为 fread() 只是把一大堆东西塞入缓存里供你使用。（这里缓存区开了有限大小1MB，所以有分次读入。文末有一劳永逸版本）

  cnt 和 Max 是缓存区的辅助变量，分别表示缓存区已经被使用到哪里、缓存区的实际容量。fread() 不需要这两个变量。这两个变量只是在 fread() 之后帮助你利用缓存区的。

• 想象一下，第一次调用 getch() 会怎么样？

  因为刚开始 cnt 和 Max 都是 0，所以执行一次 fread() 迅速读入 1048576 个字符。

  小提示：

  • 1. 很可能一次就读完了数据所有字符，如果实际数据不足 1048576 个字符也不会出错，fread() 会返回成功读入的块数。

  • 2. tmp 下标从 0 开始，即 tmp[0] 存的是第一个字符。而 fread() 返回的是成功的确切个数，所以 tmp[Max-1] 存的是读入到的最后一个字符，Max 是首个不合法位置。

• 首次读入以后很长一段时间内，调用 getch() 只需要返回 tmp[cnt]。其中 cnt++ 起到先返回、后加 1 的作用。

• getch() 用了一百多万次以后，发现 cnt 与 Max 相撞，此时再次调用 fread() 迅速读入 1048576 个字符，cnt 回到 0。

下面是指针写法，推荐指针！

#include <cstdio>
#include <cctype>
const int BUFSIZE = 1 << 20;
char ibuf[BUFSIZE], *is = ibuf, *it = ibuf;
inline char getch(){
    if(is == it)
        it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
    return is == it ? EOF : *is++;
}
inline int getint(){
    int res = 0, neg = 0, ch = getch();
    while(!(isdigit(ch) or ch == '-') and ch != EOF)
        ch = getch();
    if(ch == '-')
        neg = 1, ch = getch();
    while(isdigit(ch))
        res = res * 10 + (ch - '0'), ch = getch();
    return neg ? -res : res;
}

说明

• is 和 it 是指针，就算你之前不喜欢指针，相信也看得懂吧。数组名称也是个指针。在指针前面加一个 *，可以返回指针所指的值。

  • *ibuf 等效于 ibuf[0]，

  • *(ibuf + 1) 等效于 ibuf[1]。

  • “is = ibuf”就是让 is 指向数组 ibuf[] 的第一个位置。此后 is++ 就是让它指向数组中的下一个位置。

• 若 fread() 没有成功读入任何一个字符（is 与 it 依然相等），那就是到了文件的末尾，返回 EOF。

• 除了改用 getch()，快读本身没有变。

• 编译运行、键盘输入数据时 fread() 无法停止？因为它期望得到太多字符，键盘输入时它不知道什么时候是末尾，所以你得告诉它“已经结束输入”。按 Ctrl + Z 后再回车就好了。

普通快输

快输出场率没有快读高的？

• 读入规模大的题目不少，但输出规模大的题目不多；

• 读入数据往往格式统一，快读容易适应。但输出答案时可能有要求灵活，比如穿插字符串。这时候 printf() 的优势就很明显。

但还真有派上用场的时候……整数 fwrite() 还是有明显优化效果的。

某 NOIlinux 测试，多于两千组，clock() 计时的，没加优化。

原理

• 关于负数，在负号后方输出绝对值。

• 正向输出一个数字。通过模 10 的方式我们可以直接获得它的最后一位，然后整个数除以 10 使原来最后第二位变成最后一位。但是注意这是获取了最后一位，因此不能直接逐位输出，要暂存后倒序输出。

• 第2步中，我们不断循环获取最后一位，退出条件是当前数剩余 0，所以，如果开始时这个数就是 0，就要特判后输出一个 0。0 确实是一个特殊的数，人为规定了用一个字符表示它。

• 用 putchar() 逐位输出数字。要输出的是数字字符，而我们模 10 后得到的是数，因此输出时要加上字符 '0'(或 48)。

“当同一行中有多于一个元素时，须用单个空格符以作分隔。”

• 间隔符号，如空格、换行，要另外输出。

代码

inline void putint(int res)
{
    char q[10];

    if(res == 0)
        putchar('0');
    else
    if(res < 0)
    {
        putchar('-');
        res = -res;
    }

    int top = 0;
    while(res)
    {
        q[top++] = res % 10 + '0';
        res /= 10;
    }

    while(top--)
        putchar(q[top]);
}

• 定义临时变量

  • 传入要输出的整数 res；字符数组 q 暂存数字的各个位，以便于倒序输出。

• 特判负数和 0 的情况

• 用模 10 的方式将数字从后向前转换成数字字符

  • 除以 10 没有位运算方法。如果除以 10 有快速算法，那么模 10 也有了。
  • 注意 q[top++]，类似于上面快读的指针 is。

• 倒序输出字符

  • 注意 while(top--)，一个比较巧妙的用法，想想这个方法是怎么输出 q[0] 的——那时的 while 内，top = 1，逻辑值还是真。

用 fwrite 优化普通快输

其实只优化了 putchar()

语法

fwrite() 也在 <cstdio> 里。它把数据输出到你指定的地方。它做的也只是把现成的字符一块一块输出去。

• 给它四个参数：

  现成的东西在哪里，“每块”包含几个字节，想要输出几块，输出到哪里。

  //假设b数组存储了应该输出的字符
  fwrite(b, 1, cnt, stdout);

• 注意这里第三个参数需要是确切的字符个数。当然，它也会返回成功输出了几块。

用自己写的函数代替 putchar()。

实现

const int BUFSIZE = 1 << 20;
char tmp[BUFSIZE];
int cnt = 0;

inline void flush()
{
    fwrite(tmp, 1, cnt, stdout);
    cnt = 0;
}

inline void putch(char ch)
{
    tmp[cnt++] = ch;
    if(cnt == BUFSIZE)
        flush();
}

• 这里也有一个缓存区。在你调用 flush() 之前，putch() 只会把要输出的字符放到缓存区。在 flush() 中，fwrite() 就把缓存区的一大堆东西输出去。

  cnt 是缓存区的辅助变量，表示缓存区已经被填充了多少。

• 如果 cnt 超出上限（达到 BUFSIZE 就已经不合法了），就用 fwrite() 输出缓存区的积存，清空缓存，cnt 回到 0。

• 在缓存区满时，putch() 会自动调用 flush()。你会发现到了最后，缓存区总还存着一些东西。程序最后需要手动调用一次 flush() 输出积存，如果数组中没有积存当然也不会出错。

  int main(){
    //...
    flush();
    return 0;
  }

输出的数字之间需要间隔符，可直接以这样的方式实现

for(int i = 1; i <= n; ++i)
    putint(a[i]), putch(' ');
putch('\n');

用 fwrite() 优化字符串输出也是很好的。

参考代码

剪贴板