读写挂测试&怀疑人生

众所周知,在信息题目中,有一个非常令人头疼的问题就是TLE.同样众所周知的还有一个词语,叫做卡常数.就像这样:

“这道题时间复杂度没问题,怎么调都TLE”

“卡卡常就过了/优化优化常数就过了”

然而,有时会被针对,即使主要过程中的复杂度和常数都很优,读入的过程就已经足以使得你的程序TLE.这时候就需要读写优化了.

经验告诉我们…

一般来说,c++中的各种方式进行读写的速度对比是这样的:v(cin,cout)<v(cin,cout(关闭流同步))<v(scanf,printf)<v(读写挂).针对这一点,我进行了一些测试(然后开始怀疑人生)

生成数据

我采用了一个极为简单的程序随机生成$10^6$个整数存入文件,作为测试用的数据.程序代码如下:

1
2
3
4
5
6
7
8
9
10
11
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
int main()
{
srand(time(0));
freopen("data.in","w",stdout);
for(int i=1;i<=1000000;i++) printf("%d ",rand());
return 0;
}

对cin与cout进行测试

首先我使用cin和cout对测试数据进行读入并立刻输出至标准输出,用ctime中的clock()函数计时,并将运行时间写入文件.代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<fstream>
#include<iostream>
#include<ctime>
using namespace std;
ifstream fin("data.in");
ofstream fout("test1.out");
int main()
{
double time0=clock();
int tmp;
for(int i=1;i<=1000000;i++)
{
fin>>tmp;
cout<<tmp<<" ";
}
fout<<"Cost "<<(int)((clock()-time0)/CLOCKS_PER_SEC*1000)<<"ms."<<endl;
return 0;
}

在测试后我得到了这样的结果:

Cost 129151ms.

共花费了129151毫秒,约129秒,2分钟.

对关闭流同步的cin与cout进行测试

我同样使用cin和cout对测试数据进行读入并立刻输出至标准输出,用ctime中的clock()函数计时,并将运行时间写入文件,但这次在开始之前我先关闭了cin,cout与stdio的同步,因为这个同步操作将带来不小的时间开销.代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<fstream>
#include<iostream>
#include<ctime>
using namespace std;
ifstream fin("data.in");
ofstream fout("test2.out");
int main()
{
ios::sync_with_stdio(false); //关闭流同步
double time0=clock();
int tmp;
for(int i=1;i<=1000000;i++)
{
fin>>tmp;
cout<<tmp<<" ";
}
fout<<"Cost "<<(int)((clock()-time0)/CLOCKS_PER_SEC*1000)<<"ms."<<endl;
return 0;
}

在测试后我得到了这样的结果:

Cost 1640ms.

共花费了1640毫秒,约2秒.

对scanf与printf进行测试

这次使用scanf和printf对测试数据进行读入并立刻输出至标准输出,同样用ctime中的clock()函数计时,并将运行时间写入文件.代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
#include<ctime>
int main()
{
FILE* fin=fopen("data.in","r");
FILE* fout=fopen("test3.out","w");
double time0=clock();
int tmp;
for(int i=1;i<=1000000;i++)
{
fscanf(fin,"%d",&tmp);
printf("%d ",tmp);
}

fprintf(fout,"Cost %dms.\n",(int)((clock()-time0)/CLOCKS_PER_SEC*1000));
return 0;
}

在测试后我得到了这样的结果:

Cost 216750ms.

共花费了216750毫秒,约217秒,近4分钟.

事情的进展开始超出了我的想象.

对读写挂的测试

最后我对自己写的读写挂进行了读写测试.读写挂使用getchar(void)putchar(int _Ch)函数进行读写,这两个函数的工作速度更快,但是一次只能对一个字符进行读或写.同样从文件中读入,立刻输出至标准输出,但这次的运行时间被输出至了标准输出.虽然不甚科学,但不会对数据产生太大的影响.

代码如下:

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
54
55
56
57
58
59
#include<cstdio>
#include<ctime>
inline void get_int(int& a)
{
char c=getchar();
bool flag=0;
while(c!='-' && (c<'0' || c>'9')) c=getchar();
if(c=='-')
{
flag=1;
c=getchar();
}
a=0;
while(c>='0' && c<='9')
{
a*=10;
a+=c-'0';
c=getchar();
}
a=flag?-a:a;
return;
}

void put_int(int a)
{
if(a<0)
{
putchar('-');
a=-a;
}
if(a>9) put_int(a/10);
putchar('0'+a%10);
return;
}

inline void end_line(void){putchar('\n');}

inline void put_char(const char a[])
{
for(int i=0;a[i]!='\0';i++) putchar(a[i]);
return;
}

int main()
{
freopen("data.in","r",stdin);
int tmp;
double time0=clock();
for(int i=1;i<=1000000;i++)
{
get_int(tmp);
put_int(tmp);
putchar(' ');
}
put_char("Cost ");
put_int((int)((clock()-time0)/CLOCKS_PER_SEC*1000));
put_char("ms.\n");
return 0;
}

测试结果是这样的:

Cost 142303ms.

共花费了142303毫秒,约142秒,超过2分钟.

对比&总结

最终得到的时间数据告诉我们,实际上的速度是这样的:

v(scanf,printf)<v(读写挂)<v(cin,cout)<v(cin,cout(关闭流同步))

不禁开始怀疑人生.现在还没有找到问题所在,或许是我的读写挂太丑了?我查找了其他人写的读写挂,大部分和我的大同小异,应该没有太大影响.

等找到问题所在再来更新这篇文章吧.如果您有什么高见,请务必留下评论,感谢!本蒟蒻在此鞠躬.

本文标题:读写挂测试&怀疑人生

文章作者:Snake

发布时间:2018年03月25日 - 16:03

最后更新:2018年04月28日 - 20:04

原始链接:https://snake.moe/2018/03/25/读写挂测试&怀疑人生/

许可协议: 署名-非商业性使用-相同方式共享 4.0 国际 转载请保留原文链接及作者。