关于读入优化的最终分析

时间：2018-02-14 17:48:25 阅读：467 评论：0 收藏：0 [点我收藏+]

关于读入优化的最终分析

摘要

身为一只以卡常为生的蒟蒻，总想着通过一些奇技淫巧来掩饰优化常数。

于是本文章就非正式地从最初的开始到最终的终止来谈谈在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) 输出文件：为了避免代码的部分被过分优化，最后程序将根据输入计算一个值，然后输出这个值。详见代码。

代码

以下代码尽量按照最快的方式尽量写成函数：

  1 //cin_with_sync(true)
  2 #include <cstdio>
  3 #include <iostream>
  4 
  5 using namespace std;
  6 
  7 #define MAXN 11111111
  8 
  9 inline int test(){
 10     int recieve_int, ret = 0;
 11     for(int i = 0; i < MAXN; i++){
 12         cin >> recieve_int;
 13         ret += recieve_int;
 14     }
 15     char recieve_char;
 16     for(int i = 0; i < MAXN; i++){
 17         cin >> recieve_char;
 18         ret -= recieve_char;
 19     }
 20     return ret + 1;
 21 }
 22 
 23 
 24 int main(){
 25     freopen("fr.in", "r", stdin);
 26     printf("%d", test());
 27     fclose(stdin);
 28     return 0;
 29 }
 30 //cin_with_sync(false)
 31 #include <cstdio>
 32 #include <iostream>
 33 
 34 using namespace std;
 35 
 36 #define MAXN 11111111
 37 
 38 inline int test(){
 39     ios::sync_with_stdio(false);
 40     cin.tie(0);
 41     int recieve_int, ret = 0;
 42     for(int i = 0; i < MAXN; i++){
 43         cin >> recieve_int;
 44         ret += recieve_int;
 45     }
 46     char recieve_char;
 47     for(int i = 0; i < MAXN; i++){
 48         cin >> recieve_char;
 49         ret -= recieve_char;
 50     }
 51     return ret + 1;
 52 }
 53 
 54 
 55 int main(){
 56     freopen("fr.in", "r", stdin);
 57     printf("%d", test());
 58     fclose(stdin);
 59     return 0;
 60 }
 61 //scanf
 62 #include <cstdio>
 63 
 64 using namespace std;
 65 
 66 #define MAXN 11111111
 67 
 68 inline int test(){
 69     int recieve_int, ret = 0;
 70     for(int i = 0; i < MAXN; i++){
 71         scanf("%d", &recieve_int);
 72         ret += recieve_int;
 73     }
 74     char recieve_char;
 75     scanf("%c", &recieve_char), scanf("%c", &recieve_char);
 76     for(int i = 0; i < MAXN; i++){
 77         scanf("%c", &recieve_char);
 78         ret -= recieve_char;
 79     }
 80     return ret + 1;
 81 }
 82 
 83 
 84 int main(){
 85     freopen("fr.in", "r", stdin);
 86     printf("%d", test());
 87     fclose(stdin);
 88     return 0;
 89 }
 90 //getchar
 91 #include <cstdio>
 92 
 93 using namespace std;
 94 
 95 #define MAXN 11111111
 96 
 97 inline int read(){
 98     int num = 0;
 99     char c;
100     while((c = getchar()) < 48);
101     while(num = num * 10 + c - 48, (c = getchar()) >= 48);
102     return num;
103 }
104 
105 inline int test(){
106     int recieve_int, ret = 0;
107     for(int i = 0; i < MAXN; i++){
108         recieve_int = read();
109         ret += recieve_int;
110     }
111     char recieve_char;
112     while((recieve_char = getchar()) < 60);
113     ret -= recieve_char;
114     for(int i = 0; i < MAXN; i++){
115         recieve_char = getchar();
116         ret -= recieve_char;
117     }
118     return ret;
119 }
120 
121 
122 int main(){
123     freopen("fr.in", "r", stdin);
124     printf("%d", test());
125     fclose(stdin);
126     return 0;
127 }
128 //fread(old)
129 #include <cstdio>
130 
131 using namespace std;
132 
133 #define MAXN 11111111
134 
135 #define Finline __inline__ __attribute__ ((always_inline))
136 
137 Finline char get_char(){
138     static char buf[200000001], *p1 = buf, *p2 = buf;
139     return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 200000000, stdin), p1 == p2) ? EOF : *p1 ++;
140 }
141 inline int read(){
142     int num = 0;
143     char c;
144     while((c = get_char()) < 48);
145     while(num = num * 10 + c - 48, (c = get_char()) >= 48);
146     return num;
147 }
148 
149 inline int test(){
150     int recieve_int, ret = 0;
151     for(int i = 0; i < MAXN; i++){
152         recieve_int = read();
153         ret += recieve_int;
154     }
155     char recieve_char;
156     while((recieve_char = get_char()) < 60);
157     ret -= recieve_char;
158     for(int i = 0; i < MAXN; i++){
159         recieve_char = get_char();
160         ret -= recieve_char;
161     }
162     return ret;
163 }
164 
165 
166 int main(){
167     freopen("fr.in", "r", stdin);
168     printf("%d", test());
169     fclose(stdin);
170     return 0;
171 }
172 //fread(new)
173 #include <cstdio>
174 
175 using namespace std;
176 
177 #define MAXN 11111111
178 
179 #define Finline __inline__ __attribute__ ((always_inline))
180 
181 Finline char get_char(){
182     static char buf[200000001], *p1 = buf, *p2 = buf + fread(buf, 1, 200000000, stdin);
183     return p1 == p2 ? EOF : *p1 ++;
184 }
185 inline int read(){
186     int num = 0;
187     char c;
188     while((c = get_char()) < 48);
189     while(num = num * 10 + c - 48, (c = get_char()) >= 48);
190     return num;
191 }
192 
193 inline int test(){
194     int recieve_int, ret = 0;
195     for(int i = 0; i < MAXN; i++){
196         recieve_int = read();
197         ret += recieve_int;
198     }
199     char recieve_char;
200     while((recieve_char = get_char()) < 60);
201     ret -= recieve_char;
202     for(int i = 0; i < MAXN; i++){
203         recieve_char = get_char();
204         ret -= recieve_char;
205     }
206     return ret;
207 }
208 
209 
210 int main(){
211     freopen("fr.in", "r", stdin);
212     printf("%d", test());
213     fclose(stdin);
214     return 0;
215 }
216 //mmap
217 #include <cstdio>
218 #include <fcntl.h>
219 #include <unistd.h>
220 #include <sys/mman.h>
221 
222 using namespace std;
223 
224 #define MAXN 11111111
225 
226 #define Finline __inline__ __attribute__ ((always_inline))
227 
228 char *pc;
229 
230 inline int read(){
231     int num = 0;
232     char c;
233     while ((c = *pc++) < 48);
234     while (num = num * 10 + c - 48, (c = *pc++) >= 48);
235     return num;
236 }
237 
238 inline int test(){
239     pc = (char *) mmap(NULL, lseek(0, 0, SEEK_END), PROT_READ, MAP_PRIVATE, 0, 0);
240     int recieve_int, ret = 0;
241     for(int i = 0; i < MAXN; i++){
242         recieve_int = read();
243         ret += recieve_int;
244     }
245     char recieve_char;
246     while((recieve_char = *pc++) < 60);
247     ret -= recieve_char;
248     for(int i = 0; i < MAXN; i++){
249         recieve_char = *pc++;
250         ret -= recieve_char;
251     }
252     return ret + 1;
253 }
254 
255 
256 int main(){
257     freopen("fr.in", "r", stdin);
258     printf("%d", test());
259     fclose(stdin);
260     return 0;
261 }
262 //数据生成器
263 #include <ctime>
264 #include <cstdio>
265 #include <climits>
266 #include <algorithm>
267 
268 #define MAXN 11111111
269 
270 int main(){
271     freopen("fr.in", "w", stdout);
272     srand(time(NULL));
273     for(int i = 0; i < MAXN; i++) printf("%d ", rand() % INT_MAX);
274     puts("");
275     for(int i = 0; i < MAXN; i++) putchar(rand() % 48 + 79);
276     fclose(stdout);
277     return 0;
278 }

结果

我们在测评机下做了多次试验，调整了代码的部分细节，取最后一次测试成绩如下：

技术分享图片

分析

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，而且实际使用的时候速度更快。