快速读入

我常用的快读模板和解析。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Read()
{
#define cg ch = getchar()
int x = 0, f = 1;
char cg;
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1; // 保证输入为正数时,这句话可以省略
cg;
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48); // 相当于x = x * 10 + ch - '0'
cg;
}
return x * f; // 正负号
}

解析

这一句

1
x = (x << 1) + (x << 3) + (ch ^ 48);

x << 1 相当于 $x\times2$,x << 3 相当于 $x\times2^3=x\times8$,两个加起来就是 $2x+8x=10x$,ch ^ 48 相当于ch - '0'.


速度比较

假如有一个 丧心病狂的 输入数据,它生成的方法如下:

1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
using namespace std;

int main()
{
freopen("input.txt", "w+", stdout);
for (int i = 1; i <= 1000000; i++) cout << "12345 ";
for (int i = 1; i <= 1000000; i++) cout << "12345 ";
for (int i = 1; i <= 1000000; i++) cout << "12345 ";
return 0;
}

如下程序可以用于验证 cinscanf()Read() 快慢:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<ctime>
#include<iostream>
using namespace std;

clock_t s, e;
int a;

inline int Read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}

int main()
{
// 从input.txt中读入数据
freopen("input.txt", "r+", stdin);

// cin part
cout << "cin takes ";
s = clock();
for (int i = 1; i <= 1000000; i++) cin >> a;
e = clock();
cout << (double)(e - s) << endl;

// scanf() part
cout << "scanf() takes ";
s = clock();
for (int i = 1; i <= 1000000; i++) scanf("%d", &a);
e = clock();
cout << (double)(e - s) << endl;

// Read() part
cout << "Read() takes ";
s = clock();
for (int i = 1; i <= 1000000; i++) a = Read();
e = clock();
cout << (double)(e - s) << endl;

return 0;
}

在我的电脑上运行输出如下:

1
2
3
cin takes 1984
scanf() takes 2507
Read() takes 191

本文作者:Xecades

本文链接:https://blog.xecades.xyz/drafts/FastRead.html

文章默认使用 CC BY-NC-SA 4.0 协议进行许可,使用时请注意遵守协议。

评论