一般我们使用c++输入时,会使用scanf或cin,但其实他们是很慢的,有时候做题,即使算法优秀,但如果输入或输出时就几乎要超时,那就基本没救了。所以,对输入输出的优化是十分必要的。
还记得我们机房有一位卡常神仙,在一次比赛中,某道题难得一比(应该只是我们太菜了。。),全机房都打了暴力。众人都是20分,唯独那位神仙凭借一手高超的卡常神技以及高人一等的输入输出优化,愣是卡到了40分……
如果这个例子还不能让你认识到输入输出优化的重要性,那么,我们来看看这几种输入方式的差距:
我们采用这几种输入方式,读入10000000个整型数据(999999999),他们花费的平均时间如下:
输入方式 | 时间/ms |
---|---|
cin | 7024 |
scanf | 3417 |
getchar | 650 |
fread | 521 |
可以发现,fread的速度约是cin的14倍,scanf的7倍。
这应该是最好的证据了。
进入正题
cin和scanf的速度过慢,这里不做讨论,重点讲getchar和fread。
getchar
getchar的作用是读取一个字符,为什么它比前两个要快嘛……这个上网查查它们的运行机制就知道了。(其实是太高深了我并不会。。反正读优这种东西会用就好了~),那么打成代码的形式就是这样的:
void read(int &x)//表示读入的数据存到x这个变量中,x是引用外部的一个变量
{
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
}
烦是比scanf和cin烦了点,但是重要的是快呀~
当然,也可以用类似的方法读入浮点数或字符串,这里就不给出来了。
它虽然比fread要慢一点点,但是它有一个优点,就是容易与scanf什么的混用。这就方便很多了。
fread
fread函数中有4个参数,分别设它们为a,b,c,d,就是这样的:
fread(a,b,c,d);
它们的意义分别是:
a: 这是一个指针类型,指向一个char类型,fread会将读入读到的字符逐个逐个地塞到a、a+1、a+2、……中,这里的+1是指指针向后移一位,移的字节数根据其指针类型而定。
b: 表示读入的数据的字节数,如果我需要将读入的数据弄成char来存,那么b就等于1,但是不可以为了方便,直接将b弄成4,试图直接将整数读进来。因为fread读入的时候是将1234
这样的数字统一当做字符读进来的,如果你强行将他们的二进制编码拼凑在一起的话,是不可能得到想要的数的。
c: 如果说b表示读入的块的大小的话,那么c就表示要读多少个块。显然,我们一般不知道要读入的数据的长度,所以,这个c一般设大一点,当没有东西读入时,它自然会停下,所以不用担心出什么问题。
d: 这是也是一个指针类型,但他指向一个文件,表示我们的数据从哪里读取。一般使用stdin这个系统帮我们搞好的指针,他会在exe文件所在目录下寻找输入文件。(用就完事了~,原理什么的不用管)
然后,因为fread这个函数是有返回值的,它会返回成功读入的块数,于是,我们可以利用它乱搞。
代码示例(该代码来自那位卡常神仙):
inline char cn()
{
static char buf[10000010],*t1=buf,*t2=buf;//t1和t2表示buf中有用数据所在区间的起点和终点,注意这里一定要有static
return t1==t2&&(t2=(t1=buf)+fread(buf,1,1000000,stdin),t1==t2)?EOF:*t1++;
}
如果没看懂上面那个return的话,这里有解释:
如果t1不等于t2,那么就会进入
*t1++;
这个语句,它会返回t1这个指针所指向的那个char类型的变量的值。
但如果满足了
t1==t2
这个条件,那么就是说buf中已经没有有用的数据了,那么我们就尝试读入新的数据。也就是
t2=(t1=buf)+fread(buf,1,1000000,stdin)
这一句,首先要知道,=
运算符是有返回值的,例如a=b
,那么它的返回值就是b
也就是说,t2=(t1=buf)
这一句就相当于实现了将t1和t2的值都变成buf的操作,但是还没完,t2还要加上新读取的数据的数量,这样,t1和t2就形成了一个区间。
然后到了很重要的部分
,t1==t2
,还是要讲一个重要的前置芝士,我们要隆重地请出——逗号运算符!没错,,
也是个运算符,例如a,b,c,d,e
,它的返回值就是e,也就是最后一项,完全跟前面几项没有关系(所以它也被用来连接多个语句,如a=b,k++;
)。所以
(t2=(t1=buf)+fread(buf,1,1000000,stdin),t1==t2)
这一大串的返回值就是t1==t2
,如果尝试读取数据后,t1依然等于t2,说明已经没有数据了,那么这个时候,cn()
这个函数就会返回一个EOF,表示没有数据。
结束语
祝各位用了这些高速的读入方式后,能够水到更多分进一步优化自己的代码,在以后的c++道路上走得更辉煌。