关于 OI 中的读入优化

关于 OI 中的读入优化

起因

一个偶然的机会让我发现自己平时一直用的快读模板甚至没有 scanf 快

经过

上网查了各种奇奇怪怪的输入输出优化,在本人台式电脑(Ubuntu 20.20, AMD® Ryzen 7 3700x 8-core processor × 16)上跑了一个简单的 benchmark,源代码在此(毒瘤压行请忽略,毕竟是自己常用的板子).

列出的一共有五种读入:

  • scanf (scanf)
  • std::cin (std_istream)
  • std::cin + 取消 stdio 同步 (unsynced_std_istream)
  • 手写快读 + getchar (Primitive_MI)
  • 手写快读 + 加缓冲区的 getchar (MI)

结果

每次读入 1000000 个数,重复测试 100 次取平均值,测试结果如下:

方式 平均时间(s) 平均速度(int/s) 总时间(s)
scanf 0.0514383 19652971.755339 5.088289
std_istream 0.170506 5864898.657777 17.050593
unsynced_std_istream 0.043879 22789986.626836 4.387892
Primitive_MI 0.058276 17159684.419676 5.827613
MI 0.019742 50653095.689270 1.974213

嗯。显而易见,std::cin 常年被诟病是有章可循的,但是加上 ios::sync_with_stdio(false)cin.tie(nullptr) 两句还是能比 scanf 更优一些(毕竟是流式读入而不需要解析格式化的字符串)。

我以前一直使用的快读模板就是上文提到的 Primitive_MI,还真就比不上 scanf 了(草

加上了读入缓冲区(4KB)后的读入很明显要快很多,以后就用它当模板啦~

顺便,可以在 这里 拿到这份可以当作各种题模板的快读模板(不过默认是我 > 单个尖括号读入的习惯,也可以手动更改),同时支持各种整型,无符号整型,char(非空白字符)和 std::string(以空白字符为界)的读入。

需要注意的是,由于开了缓冲区,所以本地手动调试的时候输完数据需要输入 EOF (Linux 下按 Ctrl+D,Windows 下按 Ctrl+Z)程序才能接收到读入(线上 OJ 没有这个问题)。当然,你可以在编译器选项中加入 -DMIVIK 来取消缓冲区读入,便于调试。


2020-5-15

发现自己的模板由于加了读入缓冲却忘了处理 ungetc 导致在极端情况下出了锅,今天补上了。

作者

Mivik

发布于

2020-05-13

更新于

2021-05-31

许可协议

评论