C++的IO优化 - 零度随想

转载于c++的IO优化

不知道各位是否接触过OJ呢？或许，一段时间后你们就开始对“IO优化”蠢蠢欲动了吧。输在起跑线的感觉总是不怎么样。

先上结论：

方法	cin	cin+setvbuf	scanf	cin+关闭同步	cin+关闭同步 + setvbuf	scanf + setvbuf
时间（ms)	10800	10240	388	372	340	340

方法	手动输入	手动输入+inline	手动输入输出+inline
时间（ms)	176	144	76

其中超过1s的只是估计值——例如，在时限下只能跑完1/10的数据。另外，除最后一个，输出都是printf。

出自清华OJ

下面是详细解释：

cin 和关闭同步

cin慢吗？cin关闭同步后，一点不输scanf。那么如何关闭同步呢？只要在你的代码主函数开头加上：

1 2	`ios_base::sync_with_stdio(false); cin.tie(NULL);`

即可。cin实际上是用的C++新特性——流，而scanf是兼容C的——你甚至能看到打孔机时代留下的痕迹。如此老掉牙的事物用着显然不太安全——关于scanf的危险性，可以移步我的另一篇文章：scanf——从入门到放弃
那么cin关闭同步分为两步：

ios_base::sync_with_stdio(false);关闭C++和C标准流（即iostream和stdio.h下的I/O）的兼容性。各位可以试一下，这之后如果把cin和scanf混用，很快就会弹出segment fault。
可以看出，cin为了兼容scanf还是做了不少牺牲的。实际上这和scanf的实现有一些关系，大致是因为：在那个输入方式都不大确定，有人用键盘，有人用打孔机的时代，scanf是被交给各个系统自己实现的。因此，scanf虽然功能上是确定的，但是没有统一的接口和运作模式，cin和五花八门的scanf保持同步就显得很困难啦。
cin.tie(NULL);这使得cin和cout解绑。cin和cout的绑定实际上是为了确保在
1
2
cout<<"请输入x："; cin>>x;
这种情况下，cout能先flush输出流，再执行cin，以使用户能先在屏幕上看到“请输入x：”字样再输入。不及时flush的话，“请输入x：”可能存留在输出流中而没有显示，直接进入到cin语句，带来很不好的用户体验，因此cin和cout绑定关系是默认开启的。不过，flush也是蛮耗时的，所以打OJ追求速度的话，不妨关掉它。

可以看到，关闭同步之后，cin的用时骤降到了372ms。

setvbuf

这个特性是清华OJ在这道题里已经给出的提示：

1 2	`setvbuf(stdin,new char[1<<20],_IOFBF,1<<20); setvbuf(stdout,new char[1<<20],_IOFBF,1<<20);`

意为，开辟一块足够大的缓冲区来读写。缓冲区的好处是，输入信息会被一股脑读入缓冲区，然后再慢慢分配给每一行cin或者scanf，输出同理，每一行printf会被放入缓冲区，再一股脑打印出去。

就拿这道A+B problem为例：（题干是，输入一个数N，然后输入N对A，B，输出N个A+B）

#include<iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
//	setvbuf(stdin,new char[1<<20],_IOFBF,1<<20);
//	setvbuf(stdout,new char[1<<20],_IOFBF,1<<20);

	int N;
	cin>>N;
	for(int i=0; i<N; ++i)
	{
		int a,b;
		cin>>a>>b;
		printf("%d\n",a+b);
	}
}

如果注释掉两行setvbuf，执行效果是这样的：

输入：2
输入：1 2（回车）
输出：3
输出：3 4（回车）
输出：7

而如果取消两行注释，执行setvbuf，则是：

输入：2
输入：1 2（回车）
输出：3 4（回车）
输出：3
输出：7

这就是printf被缓存直到程序结束的结果。

为了验证，还可以在执行setvbuf的版本，试试加一行fflush：

for(int i=0; i<N; ++i)
{
	int a,b;
	cin>>a>>b;
	printf("%d\n",a+b);
	fflush(stdout);
}

就又回到了不执行setvbuf的效果。

fflush定义在cstdio头文件，就是“冲洗”那些遗留在缓冲区的内容。stdin代表输入流，stdout代表输出流；fflush(stdout); 代表把存在输出流缓冲区的东西全部“冲洗”出去，打印到屏幕上。在C++11中，fflush(stdin); 意为“冲洗”输入流，即丢弃所有用户敲进去，而没有被读入的事物，比如说：（要注释掉ios_base::sync_with_stdio(false);和cin.tie(NULL);两句话）
1
2
3
> cin>>a;
> fflush(stdin);
> cin>>b;
如果用户在输入a的时候，在一行敲了两个数，然后回车，第二个数会存留在缓冲区。如果没有第二行的fflush(stdin);，第二个数就会被读入b。然而，fflush(stdin);语句使输入缓冲区被丢弃，所以用户的第二个输入就被丢弃了，他需要再输入一个数来满足cin>>b;语句。
要注意的是，fflush(stdin);在C++11前的标准中是未定义的！C标准对fflush的定义是fflush(ostream)，也就是不支持输入流！在Windows和Linux等系统下，这一功能已经被实现了，但还一些系统，如Cygwin，就没有实现上述的fflush(stdin);功能。当然，如果你的C代码只在Windows或Linux跑——比如OJ里，那没问题，不过比较好的写法还是：
C中，stdin输入流：getchar()，getline()这样的函数，或者
C++中，iostream输入流：可以用cin >> ws去除空白字符，或者
cin.ignore(256,’\n’);或者不嫌麻烦的话，cin.ignore(numeric_limits<streamsize>::max(),’\n’);以丢弃剩余的一行（包括换行符）（前者如果迟迟没有遇到\n，最多丢弃256字符）。

采用setvbuf后，cin输入流的时间从372ms进一步降到了340ms.

手动输入

手动输入主要就是，先用unistd.h头文件下的read函数把东西全读进来，然后手写十进制解析，一个字符一个字符扫过去，提取数字。

先是比较简单的版本：

#include <iostream>
#include <unistd.h>
using namespace std;

inline int getnum(char*& poi)
{
	while(*poi<'0' || *poi>'9') ++poi;
	int s=0;
	while(*poi>='0')
	{
		s=s*10+*poi-'0';
		++poi;
	}
	return s;
}

int main()
{
	char* buf=new char[1<<20];
	int len=read(0,buf,1<<20);
	char* poi=buf;

	int N=getnum(poi);
	for(int i=0; i<N; i++)
		printf("%d\n",getnum(poi)+getnum(poi));
}

可以看到，开了个1<<20那么大的缓冲区buf，用一个指针poi扫过去，读数字的地方都写在getnum函数里了，并且加了inline提高（一点点）性能。这种输入方式在绝大部分正常问题里已经足够了，不过我们测试的那道清华OJ上，名叫“大数据（big）”的东西…他真的很big…有远超1<<20字节的输入（第四个点已经达到它的20倍以上）。

当然了，正常的OJ输入输出看到这里就够啦！毕竟OJ的输出一般就几个数，而且输入也一般不会达到1<<20个字节。

手动输入加强版

所以这里是加强版：

#include <iostream>
#include <unistd.h>
using namespace std;
#define big (1<<21)

char buf[big];
char* poi;
int len;
inline int incr()
{
	++poi;
	if(poi>=buf+len)
	{
		len=read(0,buf,big);
		poi=buf;
		fflush(stdout);
	}
}

inline int getnum()
{
	while(*poi<'0' || *poi>'9')
		incr();
	int s=0;
	while(*poi>='0')
	{
		s=s*10+*poi-'0';
		incr();
	}
	return s;
}

int main()
{
	poi=buf;
	len=read(0,buf,big);
	int N=getnum();
	for(int i=0; i<N; i++)
		printf("%d\n",getnum()+getnum());
}

在做++poi时留个心眼儿，看看是不是读完缓冲区了，如果是的话再读一次。并且，输入满了输出也就快满了，所以flush一下输出，不然输出满了一样会报内存溢出错误。为了方便，把poi，buf，len什么的都放在全局变量了。

手动输入加强版的运行时间达到了144ms。（inline关键字十分重要——如果去掉两个inline（尤其是incr的inline，incr执行了非常多次），用时直接掉到了176ms。

手动输出

思路一样：

#include <iostream>
#include <unistd.h>
using namespace std;
#define big (1<<21)

char buf[big];
char buf2[big];
int len;
char* poi=buf;
char* poi2=buf2;
int a[20];
inline int incr()
{
	++poi;
	if(poi>=buf+len)
	{
		len=read(0,buf,big);
		poi=buf;
	}
}
inline void flush()
{
	write (1,buf2,poi2-buf2);
	poi2=buf2;
}
inline int incr(char s)
{
	*poi2=s;
	++poi2;
}
inline int getnum()
{
	while(*poi<'0' || *poi>'9')
		incr();
	int s=0;
	while(*poi>='0')
		s=s*10+*poi-'0';
		incr();
	return s;
}
inline int putnum(int s)
{
	if(poi2>=buf2+big/2)flush();
	int ap=0;
	do
		a[++ap]='0'+s%10;
	while(s/=10);
	while(ap)
		incr(a[ap--]);
	incr('\n');
}

int main()
{
	len=read(0,buf,big);
	int N=getnum();
	rep(i,0,N)
	putnum(getnum()+getnum());
	flush();
}

加了个putnum和对应的另一个incr函数，并写了flush函数替换输出流fflush，使用write函数进行输出。以及，最后一定要调用一次flush函数，把残余的数据输出出去。注意，这里putnum和getnum的判断缓冲区是否满的逻辑不太一样：getnum是必须每个字符都要判断一次，因为有可能遇到读了一半的数字；而putnum中，你可以给缓冲区多开几十个字节，这样可以每次开始输出前进行判定，而不用每输出一个字符都判定一次，对性能略有改善。

这个就是最终达到76ms的版本。（排在OJ榜上第二，但是感觉已经偏题了，再优化下去也挺无聊的了。）

总结

正常的输入输出的话，只要看到“手动输入”就可以了，因为一般OJ题的输出不多，终点在输入优化，而且也没几道题丧心病狂到给你1<<20字节的测例（这可是1G的输入啊！）而且实际上，输入输出在一道正常OJ题的占比一般还是很小的。不过至少这是个能Paste到每道题的常数优化——起个心理安慰吧。

使用 GlobalSSH 加速境外服务器上一篇

scanf从入门到放弃下一篇