专栏文章

读入、输出优化的一般方法

eew3www
算法·理论参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mips2t9d
此快照首次捕获于
2025/12/03 17:01
3 个月前
此快照最后确认于
2025/12/03 17:01
3 个月前
查看原文
众所周知，C++ 的输入输出流 cin 和 cout 是十分缓慢的，那有什么方法可以优化呢？

1、取消与 stdio 的绑定（竞赛不可用）

C++ 中，cin 与 cout 默认是与 stdio 绑定的，这其实是 C++ 为了让你写代码写的舒服兼容性而采取的措施。
但是，这样一来，cin 与 cout 的读入、输出速度就会变得极其慢，喜欢用 cin 与 cout 的童鞋肯定表示不嘻嘻。
不过，万能的 C++ 早已备好了措施：ios::sync_with_stdio(0)！它可以取消 cin 与 cout 和 stdio 的绑定，故可以提升速度。
不过，这样一来，你就不能同时使用 cin 与 cout 和 scanf 与 printf，因此要理智使用。
这里以洛谷 P1923 【深基9.例4】求第 k 小的数为例。
使用 ios::sync_with_stdio(0)
不使用 ios::sync_with_stdio(0)
很容易看出来两者的差别吧。
但是，在竞赛（要开 freopen 的情况下），必须使用 stdio 来重定向输入输出，你这样一关绑定，那 freopen 不就用不了了嘛！所以，你就会喜提爆零大礼包。

2、使用 C 的输入输出

既然 iostream 慢，那我们就用 stdio 嘛！直接使用 scanf 和 printf 来读入、输出数据，速度中规中矩。
还是以洛谷 P1923 【深基9.例4】求第 k 小的数为例。
使用 stdio

3、使用 getchar 和 putchar 来进行快速读入、输出

这是重头戏！！
getchar 和 putchar 本来是针对字符的读入输出，但由于它 O(1)\mathcal{O}(1) 的时间复杂度，可以用它来快速读入、输出整数，时间复杂度 O(n)\mathcal{O}(n)，其中 nn 表示数字的位数。

快速输入

定义一个 read 函数。
CPP
void read(int &x);
首先，重复输入前面的非数字字符，判断是否为负号。
CPP
x = 0; // 初始化 x
int flag = 1;
while(!isdigit(ch)) {
    if(ch == '-') flag = -1;
    ch = getchar();
}
然后，重复循环并更新变量 xx 直到读入了非数字字符（可以使用 cctype 头文件中的 isdigit 函数）。
CPP
ch = getchar(); // 避免读入的是负号导致下面的循环进不去
while(isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
}
最后，将 xx 乘以 flagflag。
CPP
x *= flag;

快速输出

由于快速输出是要从左至右输出，而传统的取余方法是从右至左输出，我们可以写一段递归代码，利用 putchar 快速输出。
首先，定义一个 write 函数。
CPP
void write(int x)
然后，判断 xx 是否是负数。
CPP
if(x < 0) {
    putchar('-');
    x *= -1;
}
接着，递归实现从左至右输出。
CPP
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
不过，使用递归实现常数较大 （也是 STL 的通病），因此考虑采用栈来模拟这一过程。
可以定义一个手工栈，存储 xx 的每一位，最后逆序输出。
CPP
signed st[120], top = 0;
while(x > 0) {
    st[top++] = x % 10 + '0';
    x /= 10;
}
for (signed i = top - 1; i >= 0; i--) putchar(st[i]);

完整代码

CPP
void read(int &x) {
    x = 0;
	char ch = getchar();
	int flag = 1;
    while(!isdigit(ch)) {
        if(ch == '-') flag = -1;
        ch = getchar();
    }
	while(isdigit(ch)) {
    	x = x * 10 + ch - '0';
    	ch = getchar();
	}
    x *= flag;
}
void write(int x) {
    if(x < 0) {
    	putchar('-');
    	x *= -1;
	}
    signed st[120], top = 0;
	while(x > 0) {
    	st[top++] = x % 10 + '0';
    	x /= 10;
	}
	for (signed i = top - 1; i >= 0; i--) putchar(st[i]);
}
究极优化后的时间

小技巧

可以使用 C++ 中的关键字 template 来自定义读入输出的数据类型。
用法如下：
CPP
template <typename T>
// 这是你的代码，其中 T 可以视作一个普通的数据类型关键字来使用
例：
CPP
template <typename T>
void read(T &x) {
    x = 0;
	char ch = getchar();
	int flag = 1;
    while (!isdigit(ch)) {
        if(ch == '-') flag = -1;
        ch = getchar();
    }
	while (isdigit(ch)) {
    	x = x * 10 + ch - '0';
    	ch = getchar();
	}
    x *= flag;
}
template <typename T>
void write(T x) {
    if (x >= 0 && x < 10) {
        putchar(x + '0');
        return ;
    } 
    if (x < 0) {
    	putchar('-');
    	x *= -1;
	}
    int st[120], top = 0;
	while (x > 0) {
    	st[top++] = x % 10 + '0';
    	x /= 10;
	}
	for (int i = top - 1; i >= 0; i--) putchar(st[i]);
}
这样，这段快读快写代码无论什么数据类型都能用了。
注：<template> 关键字因涉及到类型判定，会让程序运行时间略微增加 1~10 毫秒，如果想要卡常的话还是尽量不要用 <template> 了。

Update 2025.5.11\text{Update 2025.5.11}

修复了一处代码错误。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...