Java教程

浅谈超快读

本文主要是介绍浅谈超快读,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
inline int read() {
	int x = 0;
	char c = getchar();
	for (; c < '0' || c > '9'; c = getchar());
	for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c ^ 48), c = getchar());
	return x;
}

这是一个我们平常使用的快读,他也能几乎达到所有题目的要求。但是有一些题目,比如没有加单调队列的跳房子,在我校机房的土豆评测机上经常会被卡掉一个点,而且时间就差一点,于是超快读就进入了我的必备模板。


我们知道,getchar是每次读出一个字符,若是我们能一次性读进一大串字符,那样效率就会快很多。
cstdio里有一个fread函数正好能满足我们的需要。这个函数的原型是这样的:

size_t fread ( void * ptr, size_t size, size_t count, FILE * stream );

看不懂没关系,我们慢慢解释。第一个形参为读入数据存放的位置,我们一般用数组指针传入;第二个形参为每个数据的长度,单位是字节,如char就是1;第三个形参是理想情况下(输入数据量充足)读入多少个数据;第四个形参是读入数据的位置,也就是指定输入流,通常为stdin。这个函数的返回值为实际读入数据的个数。
那么,稍稍改进一下我们的getchar吧。

char buf[1 << 20], *_now = buf, *_end = buf;
//buf是缓冲数组,就是读入的一串数据存放的地方;_now是字符指针,指向当前想取的那个字符;_end也是字符指针,指向这一串字符的最后一个。
inline char getchar() {
	if (_now == _end) {//如果这一串数据处理完了
		_end = _now = buf;
		_end += fread(buf, 1, 1 << 20, stdin);//那就再读一串,注意指针要回归原位
		if(_now == _end) {//如果没有读进来,就说明没有数据了
			return EOF;
		}
	}
	return *_now++;
}

把这个加到快读的前面就成超快读了,当然getchar的命名要改一下。


你可能会说,我的快读已经很长了,再加上这一段,岂不是……
没事,接下来我们来压下代码,需要用到,&&两个运算符。

首先是,运算符,这个我们一般在写条件时用到,用,并列的语句,判断真假时只取最后一个。

for (int i = 1; i <= 10, i <= 14, i <= 6; ++i)
	cout << i << endl;

输出是:

1
2
3
4
5
6

其次是&&运算符,这里有一个短路求值的概念,即当且仅当左侧运算对象无法确定表达式的结果时才会计算右侧运算对象的值。

int a = 0;
if(10 > 20 && (a += 1, 1));//后半句没有参与表达式的运算
if(10 < 20 && (a += 2, 1));//后半句参与了表达式的运算
cout << a << endl;

输出为:

2

所以代码就压成了:

char buf[1 << 20], *_now = buf, *_end = buf;
inline char _getchar() {
	return _now == _end && (_end = (_now = buf) + fread(buf, 1, 1 << 20, stdin), _now == _end) ? EOF : *_now++;
}

当然你也可以使用宏定义,这样就不用改getchar的命名了。

char buf[1 << 20], *_now = buf, *_end = buf;
#define getchar() (_now == _end && (_end = (_now = buf) + fread(buf, 1, 1 << 20, stdin), _now == _end) ? EOF : *_now++)

写在最后:

  • 此快读一般用于文件读写。
  • buf数组开小了会影响速度(会读很多次),开大了会MLE,所以请根据题目和输入数据范围随机应变,一般 \(2^{20}\) 到\(2^{23}\) 为适。
  • 附一张读入十万随机数据的速度:
输入方式 cin scanf cin(解绑) 快读 超快读(buf[1<<2] 超快读(buf[1<<20]
速度/ms 140 110 23 34 15 5
参考文献:
[http://www.cplusplus.com/reference/cstdio/fread/](fread - C++ Reference)
[https://docs.microsoft.com/en-us/previous-versions/jj987785(v=vs.140)](operator&& Operator (C++ REST SDK))
这篇关于浅谈超快读的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!