Weily's blog I write, therefore I am.

读入/输出优化

3 min read weily misc

本文所有代码默认 #include <iostream> 且 using namespace std;

帮 N 老师搞完 Fast IO 页面后有感而发，希望系统地写一下文件读入输出优化。

读入/输出优化原理

cin/cout 的速度

为啥 cin/cout 那么慢？C++ 不是 C plus plus 吗？怎么 IO 速度反而变慢了？

实际上，这是 C++ 为实现向下兼容做出的保守措施：cin/cout 保证与 printf/scanf 混用时是线程安全的。

即：如果你先调用 cout，再调用 printf，会保证前者先于后者输出；反之亦然。

通常，我们认为，C++ 风格的输入输出是 C 风格的输入输出耗时的 3 倍左右（毕竟你带着小孩玩肯定不如自己玩爽）。

因此，就有了第一种优化：

printf/scanf 优化

既然 C++ 风格的输入输出慢，我不用他不就行了？

我们可以用 printf/scanf 替代 cout/cin，达到加速读写的目的。

不过 C 风格输入输出不够智能，需要在格式化字符串中指定输入类型，万一 #define int long long 之后下意识用了 %d 而不是 %lld，那就应了那句老话：

十年 OI 一场空，不开 long long 见祖宗。

不过 C 风格的输出应付浮点数比较方便。

ios::sync_with_stdio(false) 优化

我还是想用 C++！

但是慢怎么办？

既然因为要兼顾 C 才慢，我不管 C 不就行了？

函数 ios::sync_with_stdio 可以设置标准 C++ 流是否与标准 C 流在每次输入/输出操作后同步。

只要在进行 IO 操作之前调用 ios::sync_with_stdio(false)，即可使 C++ 摆脱 C。

有关“同步”的内容可能实际更加复杂，参阅 cppreference。

endl/flush/tie 优化

还是不够快！

试试 cin.tie(0)！

默认情况下，cin 和 cout 是“绑定”在一起的，即，每次调用 cin，会在读入数据前刷新 cout 的缓冲流。

多次刷新缓冲流最终会使程序变慢。

使用 cin.tie(0) 可以改变这一点，他会取消 cin 和 cout 的绑定。

为了使程序不再主动进行不必要的刷新，我们需要使用 '\n' 替代 endl，后者在换行的同时会调用 flush。

但是！如果我们在做交互题，我们往往需要让程序刷新缓冲流。这时手动调用 flush 即可。

使用 sync_with_stdio(false) + tie(0) 后的 C++ 风格读入输出通常比 C 风格读入输出快一点。

函数调用开销

无论是 C++ 风格的读入输出，还是 C 风格的，都封装了多层函数，来应对复杂的读入输出环境。

可是，实际上，OI 界的读入输出并没有那么复杂，这无疑是一种浪费。

因此，我们可以调用更底层的 getchar/putchar 来加快读写：

getchar/putchar 优化 

inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  for (; c < '0' || '9' < c; c = getchar())
    if (c == '-') f *= -1;
  for (; '0' <= c && c <= '9'; c = getchar())
    x = x * 10 + (c ^ '0');
  return x * f;
}
void print(int x) {
  if (x < 0) putchar('-'), print(-x);
  else if (x < 10) putchar(x ^ '0');
  else print(x / 10), putchar((x % 10) ^ '0');
}

如果保证读入的数是非负数，read 可以进一步优化：

inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  for (; c < '0' || '9' < c; c = getchar())
    if (c == '-') f *= -1;
  for (; '0' <= c && c <= '9'; c = getchar())
    x = x * 10 + (c ^ '0');
  return x * f;
}

同时，应考虑使用数组模拟栈防止递归开销：

inline void print(long long x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) putchar(sta[--top] + '0');
}

文件 IO

众所周知，计算机中，离 CPU 越近，空间越小，读写越快。

例如，硬盘离 CPU 最远，读写最慢，但是，硬盘可以轻松存储十几甚至几百几千 G 的大文件，并且断电后不丢失。

内存离 CPU 很近，读写比硬盘快得多，可是，内存总共可能才 4G，OI 题中顶天让你用 1G；并且，内存数据在断电后会缓慢丢失。

缓存离 CPU 更近，读写比内存还快，空间更小。一般，如果 CPU 认为一段内存可能会多次使用，就会将它加载到缓存，提高数据处理速度，有些算法“缓存命中率”高，就是说这种算法可以充分利用这种性质。计算机中有多级缓存，大小从 1K 到 1M 不等。

寄存器可能离 CPU 最近，最多就十几个 64 位变量，速度最快，效率最高。

为啥说这个？因为 getchar/putchar 再底层，也是对硬盘操作，我们要尽量减少这样的操作。

咋再减少？只有手动模拟一个巨大的缓冲区，一次读入/输出大量数据。

fread/fwrite 优化 

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

这段代码实现了名为 buf 的读入缓冲区，一次从设备读入上百万个字符；并维护了缓冲区末尾指针 p2 和当前指针 p1。

使用宏 gc 从缓冲区获得字符。

char pbuf[1 << 20], *pp = pbuf;
void pc(const char &c) {
  if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
  *pp++ = c;
}

这段代码维护了名为 pbuf 的输出缓冲区，在缓冲区满时自动输出并清空。

使用 pc 向缓冲区写入字符。

注意在结束程序前要使用 fwrite(pbuf, 1, pp - pbuf, stdout) 手动清空一次。

这种方式的具体实现：参见我的 fastioForOI 项目。