快速读写(以C语言为例)
参考：快读攻略（详） - 学委 的博客 - 洛谷博客 (luogu.com.cn)
C语言原本的输入输出函数
scanf、printf由于考虑了很多复杂情况（例如①格式化字符串解析②错误处理③缓冲区刷新等），导致在读写位数较大的数据时速度较慢，故自己写一些速读、速写函数增加特定程序的运行速度
1. 快读
1.1 快读原理
-
数字之间用
空格或者换行符来分隔。 -
关于负数，负号后面是它的绝对值。
-
由于数字正向给出，所以要读入 256 可以这样：
- 读入 2，记录 2。
- 读入 5，先把之前的记录乘以 10，然后加上 5。现在记录了 25。
- 读入 6，先把之前的记录乘以 10，然后加上 6。现在记录了 256。
- 读到空格、换行符或者 EOF（读不到东西），就可以返回结果：256。
-
我们用
getchar()逐个读进数字字符，再减去字符 ‘0’(ASCII码为 48) 即得对应的数字。
1.2 基础实现
#include
#include
int getint()
{
int res = 0, neg = 0, ch = getchar();
while(!(isdigit(ch) or ch == '-') and ch != EOF)
ch = getchar();
if(ch == '-')
neg = 1, ch = getchar();
while( isdigit(ch) )
res = res * 10 + (ch - '0'), ch = getchar();
return neg ? -res : res;
}
程序分析：现在该段程序对时间复杂度影响最大的为getchar()函数
1.3 利用fread优化普通快读（优化getchar()函数）
1.3.1 fread()函数详解
size_t fread(void *ptr, size_t size, size_t count, FILE *stream);
fread函数的作用是从指定的文件流 stream 中读取数据，并将读取的数据存储到 ptr 指向的内存块中。它的参数含义如下：
-
ptr：指向存储读取数据的内存块的指针。 -
size：每个元素的大小（字节数）。 -
count：要读取的元素个数。 -
stream：要读取数据的文件流。
1.3.2 利用fread()函数替代基础实现中的getchar()函数
#include
#define BUFSIZE (1 << 20) // 1048576
char tmp[BUFSIZE];
int cnt = 0, Max = 0;
char getch()
{
if (cnt == Max) //第一次输入的情况
{
cnt = 0;
Max = fread(tmp, 1, BUFSIZE, stdin);
}
return tmp[cnt++];
}
1.3.3 嵌入getch()的指针写法快读
#include
#include
#define BUFSIZE (1 << 20)
char ibuf[BUFSIZE], *is = *ibuf[0], *it = *ibuf[0];
char getch() {
if (is == it) {
it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
}
return (is == it) ? EOF : *is++;
}
int getint() {
int res = 0;
int neg = 0;
int ch = getch();
while (!(isdigit(ch) || ch == '-') && ch != EOF) {
ch = getch();
}
if (ch == '-') {
neg = 1;
ch = getch();
}
while (isdigit(ch)) {
res = res * 10 + (ch - '0');
ch = getch();
}
return neg ? -res : res;
}
编译运行、键盘输入数据时 fread() 无法停止？因为它期望得到太多字符，键盘输入时它不知道什么时候是末尾，所以你得告诉它“已经结束输入”。按 Ctrl + Z 后再回车就好了。
2. 快输
2.1 快输原理
-
关于负数，在负号后方输出绝对值。
-
正向输出一个数字。通过模 10 的方式我们可以直接获得它的最后一位，然后整个数除以 10 使原来最后第二位变成最后一位。但是注意这是获取了最后一位，因此不能直接逐位输出，要暂存后倒序输出。
-
第2步中，我们不断循环获取最后一位，退出条件是当前数剩余 0，所以，如果开始时这个数就是 0，就要特判后输出一个 0。0 确实是一个特殊的数，人为规定了用一个字符表示它。
-
用
putchar()逐位输出数字。要输出的是数字字符，而我们模 10 后得到的是数，因此输出时要加上字符 ‘0’(或 48)。“当同一行中有多于一个元素时，须用单个空格符以作分隔。” -
间隔符号，如空格、换行，要另外输出。
2.2 基础实现
inline void putint(int res)
{
char q[10];
if(res == 0)
putchar('0');
else
if(res < 0)
{
putchar('-');
res = -res;
}
int top = 0;
while(res)
{
q[top++] = res % 10 + '0';
res /= 10;
}
while(top--)
putchar(q[top]);
}
2.3 利用fwrite优化普通快输（优化putchar()函数）
2.3.1 fwrite()函数详解
size_t fwrite(const void *ptr, size_t size, size_t count, FILE *stream);
fwrite函数接受四个参数：
-
ptr：指向要写入数据的内存块的指针。 -
size：要写入的每个数据项的大小（以字节为单位）。 -
count：要写入的数据项的数量。 -
stream：指向目标文件的指针。
fwrite函数将count个数据项（每个大小为size字节）从ptr指向的内存块写入到由stream指向的文件中。它返回成功写入的数据项数量。如果返回的数量与count不一致，可能表示写入过程中发生了错误。
2.3.2 利用fwrite()函数替代基础实现中的putchar()函数
#include
#define BUFSIZE (1 << 20)
char tmp[BUFSIZE];
int cnt = 0;
void flush()
{
fwrite(tmp, 1, cnt, stdout);
cnt = 0;
}
void putch(char ch)
{
tmp[cnt++] = ch;
if (cnt == BUFSIZE)
flush();
}
