摘要
身为一只以卡常为生的蒟蒻, 总想着通过一些奇技淫巧来掩饰优化常数
于是本文章就非正式地从最初的开始到最终的终止来谈谈在 OI 种各种主流非主流读入的速度以及利弊
序言
随着算法的发展各种数据结构等劲题出现, 这些题除了思维难度的提高还带来者输入数据的增多 (特别的有: uoj.ac 上的一道题需要选手自己生成数据, 而数论题往往输入较少), 对于有追求有理想的选手快速读入是必不可少的技能
尽管市面上有不同的主流读入优化, 但是大多都是基于 fread 的, 其余的只是一些小变动
而笔者就在不久之前发现更快但是非主流的 mmap(在 sys/mman.h 中) 函数, 此函数比目前已知所有读入都快
现在, 我们从入门的 cin_with_sync(true) 然后到进阶的 cin_with_sync(false), 再到标准的 scanf 然后到 getchar, 再到 fread(old), 再是 fread(new), 最后是 mmap 的原理及分析
标准
本次测试在以下环境进行:
硬件:
a) VM WorkingStation Pro 14 虚拟机
b) 基于 Ubuntu 14.04 LTS 32 位 的 NOI Linux 1.4.1
c) 内存 1003.1MiB, 硬盘 19.9GB,CPU Intel? Core? i7-6498DU CPU @ 2.50GHz,GPU Gallium 0.4 on SVGA3D; build: RELEASE;
软件: a) 编译器 G++ posix gcc version 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04)
b) 测评器: Project Lemon v1.2 测试版
c) 编译命令: g++ -o %s %s.*(不加入 - std=c++11 的原因是因为 c++11 标准会忽略部分例如 register 的语句, 同时 NOI 的编译命令也没有此条)
文件: a) 输入文件: 两组, 大小分别为 127585438 Byte 和 127582201 Byte, 前半部分为 11111111 个不超过 INT_MAX(在 climits 内) 的非负整数, 用空格分隔, 中间一个换行符, 紧接着一行由 11111111 个 id>=48 的字符组成
b) 输出文件: 为了避免代码的部分被过分优化, 最后程序将根据输入计算一个值, 然后输出这个值详见代码
代码
以下代码尽量按照最快的方式尽量写成函数:
- //cin_with_sync(true)
- #include < cstdio > #include < iostream >
- using namespace std;
- #define MAXN 11111111
- inline int test() {
- int recieve_int,
- ret = 0;
- for (int i = 0; i < MAXN; i++) {
- cin >> recieve_int;
- ret += recieve_int;
- }
- char recieve_char;
- for (int i = 0; i < MAXN; i++) {
- cin >> recieve_char;
- ret -= recieve_char;
- }
- return ret + 1;
- }
- int main() {
- freopen("fr.in", "r", stdin);
- printf("%d", test());
- fclose(stdin);
- return 0;
- }
- //cin_with_sync(false)
- #include < cstdio > #include < iostream >
- using namespace std;
- #define MAXN 11111111
- inline int test() {
- ios: :sync_with_stdio(false);
- cin.tie(0);
- int recieve_int,
- ret = 0;
- for (int i = 0; i < MAXN; i++) {
- cin >> recieve_int;
- ret += recieve_int;
- }
- char recieve_char;
- for (int i = 0; i < MAXN; i++) {
- cin >> recieve_char;
- ret -= recieve_char;
- }
- return ret + 1;
- }
- int main() {
- freopen("fr.in", "r", stdin);
- printf("%d", test());
- fclose(stdin);
- return 0;
- }
- //scanf
- #include < cstdio >
- using namespace std;
- #define MAXN 11111111
- inline int test() {
- int recieve_int,
- ret = 0;
- for (int i = 0; i < MAXN; i++) {
- scanf("%d", &recieve_int);
- ret += recieve_int;
- }
- char recieve_char;
- scanf("%c", &recieve_char),
- scanf("%c", &recieve_char);
- for (int i = 0; i < MAXN; i++) {
- scanf("%c", &recieve_char);
- ret -= recieve_char;
- }
- return ret + 1;
- }
- int main() {
- freopen("fr.in", "r", stdin);
- printf("%d", test());
- fclose(stdin);
- return 0;
- }
- //getchar
- #include < cstdio >
- using namespace std;
- #define MAXN 11111111
- inline int read() {
- int num = 0;
- char c;
- while ((c = getchar()) < 48);
- while (num = num * 10 + c - 48, (c = getchar()) >= 48);
- return num;
- }
- inline int test() {
- int recieve_int,
- ret = 0;
- for (int i = 0; i < MAXN; i++) {
- recieve_int = read();
- ret += recieve_int;
- }
- char recieve_char;
- while ((recieve_char = getchar()) < 60);
- ret -= recieve_char;
- for (int i = 0; i < MAXN; i++) {
- recieve_char = getchar();
- ret -= recieve_char;
- }
- return ret;
- }
- int main() {
- freopen("fr.in", "r", stdin);
- printf("%d", test());
- fclose(stdin);
- return 0;
- }
- //fread(old)
- #include < cstdio >
- using namespace std;
- #define MAXN 11111111
- #define Finline __inline__ __attribute__((always_inline))
- Finline char get_char() {
- static char buf[200000001],
- *p1 = buf,
- *p2 = buf;
- return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 200000000, stdin), p1 == p2) ? EOF: *p1++;
- }
- inline int read() {
- int num = 0;
- char c;
- while ((c = get_char()) < 48);
- while (num = num * 10 + c - 48, (c = get_char()) >= 48);
- return num;
- }
- inline int test() {
- int recieve_int,
- ret = 0;
- for (int i = 0; i < MAXN; i++) {
- recieve_int = read();
- ret += recieve_int;
- }
- char recieve_char;
- while ((recieve_char = get_char()) < 60);
- ret -= recieve_char;
- for (int i = 0; i < MAXN; i++) {
- recieve_char = get_char();
- ret -= recieve_char;
- }
- return ret;
- }
- int main() {
- freopen("fr.in", "r", stdin);
- printf("%d", test());
- fclose(stdin);
- return 0;
- }
- //fread(new)
- #include < cstdio >
- using namespace std;
- #define MAXN 11111111
- #define Finline __inline__ __attribute__((always_inline))
- Finline char get_char() {
- static char buf[200000001],
- *p1 = buf,
- *p2 = buf + fread(buf, 1, 200000000, stdin);
- return p1 == p2 ? EOF: *p1++;
- }
- inline int read() {
- int num = 0;
- char c;
- while ((c = get_char()) < 48);
- while (num = num * 10 + c - 48, (c = get_char()) >= 48);
- return num;
- }
- inline int test() {
- int recieve_int,
- ret = 0;
- for (int i = 0; i < MAXN; i++) {
- recieve_int = read();
- ret += recieve_int;
- }
- char recieve_char;
- while ((recieve_char = get_char()) < 60);
- ret -= recieve_char;
- for (int i = 0; i < MAXN; i++) {
- recieve_char = get_char();
- ret -= recieve_char;
- }
- return ret;
- }
- int main() {
- freopen("fr.in", "r", stdin);
- printf("%d", test());
- fclose(stdin);
- return 0;
- }
- //mmap
- #include < cstdio > #include < fcntl.h > #include < unistd.h > #include < sys / mman.h >
- using namespace std;
- #define MAXN 11111111
- #define Finline __inline__ __attribute__((always_inline))
- char * pc;
- inline int read() {
- int num = 0;
- char c;
- while ((c = *pc++) < 48);
- while (num = num * 10 + c - 48, (c = *pc++) >= 48);
- return num;
- }
- inline int test() {
- pc = (char * ) mmap(NULL, lseek(0, 0, SEEK_END), PROT_READ, MAP_PRIVATE, 0, 0);
- int recieve_int,
- ret = 0;
- for (int i = 0; i < MAXN; i++) {
- recieve_int = read();
- ret += recieve_int;
- }
- char recieve_char;
- while ((recieve_char = *pc++) < 60);
- ret -= recieve_char;
- for (int i = 0; i < MAXN; i++) {
- recieve_char = *pc++;
- ret -= recieve_char;
- }
- return ret + 1;
- }
- int main() {
- freopen("fr.in", "r", stdin);
- printf("%d", test());
- fclose(stdin);
- return 0;
- }
- // 数据生成器
- #include < ctime > #include < cstdio > #include < climits > #include < algorithm >
- #define MAXN 11111111
- int main() {
- freopen("fr.in", "w", stdout);
- srand(time(NULL));
- for (int i = 0; i < MAXN; i++) printf("%d", rand() % INT_MAX);
- puts("");
- for (int i = 0; i < MAXN; i++) putchar(rand() % 48 + 79);
- fclose(stdout);
- return 0;
- }
结果
我们在测评机下做了多次试验, 调整了代码的部分细节, 取最后一次测试成绩如下:
分析
cin_with_sync(true) 固然慢, 其原因是因为为了其保持和 scanf 等函数的输出保持同步, 所以一直会刷新流, 所以固然慢然而由于 cin 比较智能, 所以用它也有理由, 而且使用 cout 输出 long long 会比 printf 快不少
所以 cin_with_sync(false) 会快不少的原因同上
然而我们惊奇地发现 scanf 竟然比 cin_with_sync(false) 慢!? 其实在实际测试过程中, 两者的速度不相上下, 都是差不多的
getchar 是笔者第一个学的快读, 然后其实在实际使用中这种快读比 scanf 的优势更为明显, 特别是在分散读入的时候然而现在两者跑出了仅差 0.2s 的成绩, 其实也不用惊讶, 因为在以前的 scanf 的实现主要在 loc_incl.h 内的_doscan 函数内, 观察这个函数发现它就是你的快读的整合版
fread(old) 利用 fread 函数把所有输入一次性输入到程序内的缓存数组然后用 getchar 式快读调用好处就是文件操作少, 因而速度快
fread(new) 和 fread(old) 的唯一区别就是 fread(new) 只读了一次文件, 而 fread(old) 允许读多次 fread(old) 实际上是为了防止数据分几次输入, 然而因而函数较长, 不太有可能被 inline 优化而 fread(new) 则可以避免这些同时在实际使用中, fread(new) 也具有更快的速度
mmap 基于 Linux 的黑科技, 直接将文件映射到内存操作, 中间不需要阻塞系统调用, 不需要内核缓存, 只需要一次 lseek, 因而有更优的速度, 是极限卡常者不二选择在 fread(new) 已经非常快的情况下再甩 36m, 而且实际使用的时候速度更快
总结
对于初学者来说, cin 和 scanf 足矣
可以发现 getchar 是所有方法中空间最小的, 因为它的实现不需要 scanf 那样把所有情况枚举出来, 也不需要额外数组, 适用于日常生活
而 fread 是在各个平台下都可以使用的一个比较快速的读入方式, 同时在 gdb 中, fread 需要使用 EOF, 而这就可以方便文本终端中一次性把数据输入 gdb 同时你可以用缓存数组进行一些更高级的操作
mmap 只能在 Linux 下使用, 而且不接受键盘读入 , 建议在确保程序无误后使用
来源: http://www.bubuko.com/infodetail-2498465.html