Xecades
主页 文章 归档 留言 开往 RSS

快速读入

2019-11-10

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

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;
}

如下程序可以用于验证 cin、scanf() 和 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 协议进行许可，使用时请注意遵守协议。

更新于 2024-10-30

♯

评论