记一次由Java读写速度引发的TLE的一点探索

:TLE 是 Time Limit Exceeded 的缩写,即时间超限,表示你提交的程序运行使用了超出题目限定的时间

偶然间做了道水题,题目在此

题目

我的思路很简单,建一个学生对象数组,在读入数据时把数据存入一个对象里,然后再根据试机座位号码输出对应数据即可。

第一次提交

因为我并不是 ACM 选手,刷题纯属兴趣,而我的主要语言是 Java 和 Kotlin,所以我的 Java 代码是这样的

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
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
static class Stu {
long id;
int exam;

public Stu(long id, int exam) {
this.id = id;
this.exam = exam;
}

public String toString() {
return "" + id + " " + exam;
}
}

public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
while (in.hasNextInt()) {
int N = in.nextInt();
Stu[] stus = new Stu[N + 1];
for (int i = 1; i <= N; i++) {
long id = in.nextLong();
int test = in.nextInt();
int exam = in.nextInt();
stus[test] = new Stu(id, exam);
}

int M = in.nextInt();
for (int i = 1; i <= M; i++) {
System.out.println(stus[in.nextInt()]);
}
}
}
}

就是读入和输出,基本没什么逻辑可言,但是很不幸



TLE!?😨这道几乎没什么逻辑的题怎么会超时呢?🤔

第二次提交

我思考了一会,那问题只能是出在读写上了。我在输入的时候,使用 BufferedInputStream 这个包装了输入流,应该要比直接用 Scanner 输入要快的,那么应该是在输出的时候出了问题,那么我就是用 PrintWriter 来替换原本的输出好了,下面是更改过后的代码

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
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream; // IDEA 自动导的包
import java.io.PrintWriter; // IDEA 自动导的包
import java.util.Scanner;

public class Main {
static class Stu {
long id;
int exam;

public Stu(long id, int exam) {
this.id = id;
this.exam = exam;
}

public String toString() {
return "" + id + " " + exam;
}
}

public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); // 使用 PrintWriter,并使用了缓冲流加快输出
while (in.hasNextInt()) {
int N = in.nextInt();
Stu[] stus = new Stu[N + 1];
for (int i = 1; i <= N; i++) {
long id = in.nextLong();
int test = in.nextInt();
int exam = in.nextInt();
stus[test] = new Stu(id, exam);
}

int M = in.nextInt();
for (int i = 1; i <= M; i++) {
out.println(stus[in.nextInt()]); // 输出
}
out.flush(); // 将读到的内容从缓冲区输出
}
}
}

这样总该没问题了吧



WTF!?说实话,当时我都觉得这道题就是来坑 Java 选手的 🙃

Google 一下

没办法,只能请教 Google 大爷了,Google 搜索 Java in ACM TLE, how to improve input and output speed (原谅我的英语渣😅

首先,我在 GeeksForGeeks 中看到了这个 Fast I/O in Java in Competitive Programming

在文章的开头,作者还吐槽了一下 Java 的读写速度 😂



很感谢文章作者提供的思路和代码

作者在文中第二点中提到了使用 BufferedReader 和 StringTokenizer,他是这么解释的

BufferedReader – (fast, but not recommended as it requires lot of typing): The Java.io.BufferedReader class reads text from a character-input stream, buffering characters so as to provide for the efficient reading of characters, arrays, and lines. With this method we will have to parse the value every time for desired type. Reading multiple words from single line adds to its complexity because of the use of Stringtokenizer and hence this is not recommended. This gets accepted with a running time of approx 0.89 s.but still as you can see it requires a lot of typing all together and therefore method 3 is recommended.

大致意思就是,BufferedReader 从字符输入流中读取文本,缓冲字符以提供字符、数组和行的有效读取,但是用这种方式读取每次都要解析所需的类型的值,因此使用了 Stringtokenizer 这个类,不过这个方法需要大量输入,所以作者建议使用文章的第三种方法

大家可以去看看第三点,你可以直接看代码,作者定义了一个 FastReader 类,包装了 BufferedReader 和 StringTokenizer,使得起来跟 Scanner 差不多,并且文中作者很推荐这种方法,表示容易记忆并且对大多数遇到的竞赛题目都足够快

this method is very much recommended as it is easy to remember and is fast enough to meet the needs of most of the question in competitive coding.

因为作者将这个 FastReader 类包装成了内部类,所以下面就直接展示这个内部类

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
static class FastReader
{
BufferedReader br;
StringTokenizer st;

public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}

String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt()
{
return Integer.parseInt(next());
}

long nextLong()
{
return Long.parseLong(next());
}

double nextDouble()
{
return Double.parseDouble(next());
}

String nextLine()
{
String str = "";
try
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
}

虽然作者说很好记,但是,emmmm ……🤨

代码思路不难理解,基本就是把 BufferedReader 和 StringTokenizer 的操作进行了一个包装,理解了思路,敲起来还算顺手,只是为了读入快那么一点,就要写这么多总觉得不划算

第三次提交

理解了思路过后,最后修改代码

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
60
61
62
63
64
65
66
67
import java.io.*;
import java.util.StringTokenizer;

public class Main {
static class Stu {
long id;
int exam;

public Stu(long id, int exam) {
this.id = id;
this.exam = exam;
}

public String toString() {
return "" + id + " " + exam;
}
}

public static void main(String[] args) {
FastReader in = new FastReader();
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

int N = in.nextInt();
Stu[] stus = new Stu[N + 1];
for (int i = 1; i <= N; i++) {
long id = in.nextLong();
int test = in.nextInt();
int exam = in.nextInt();
stus[test] = new Stu(id, exam);
}

int M = in.nextInt();
for (int i = 1; i <= M; i++) {
out.println(stus[in.nextInt()]);
}
out.flush();
}

static class FastReader {
BufferedReader br;
StringTokenizer st;

public FastReader() {
br = new BufferedReader(new
InputStreamReader(System.in));
}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}
}
}

把不用的方法去掉,再次提交



🎉哇,可算通过了,不过就这么个问题 Java 用了这么长的代码,估计 C/C++ 要偷笑了

在上面那篇文章中,作者还提到了第四点,他封装了一个 Reader 类,但是那代码量就更多了,当然速度更快,不过作者也不建议这种方法,大家感兴趣的可以自己去看看

在 Quora 中看到的问题

此外,我还在 Quora 中还看到了这个问题



答主也在回答中对输入做了分点,在后面依然是提到了采用自定义输入类包装 BufferedReader 来提高输入速度。他封装了一个叫 FastScanner 的内部类,不过代码量也不少,这是他的代码文本连接,感兴趣的可以参考一下 这个

提高输出速度的建议

在这篇回答的最后,答主还提到了提高输出速度的方法,就是我之前提到的使用 PrintWriter 来代替传统的 System.out.println(),同时要记得在所有输出操作结束时调用 flush() 方法,但是过于频繁的调用也有可能引发 TLE

总结

题目本身不难,一般写工程的时候也没有太刻意去提高 I/O 速度,当然我觉的也是我修为不够,还没到那一步,所以在遇到这一道题时,碰到 TLE 的确有点不知所措,我觉得这也算是一个考察点吧,正好了解了如何提高 Java I/O 速度的一点小技巧。

一般情况下,用 Scanner in = new Scanner(new BufferedInputStream(System.in));做输入是足够的,因为写过的题也不少,碰到这种因为输入导致的超时也是第一次,如果某题卡时间真的很紧,那么再考虑用自定义类包装 BufferedReader 的方式,毕竟这种方式虽快,但是代码量也多了不少。

同样的,如果时间卡的不紧的话,用传统的 System.out.println() 我觉得也能应付,当然为了防止输出问题导致超时的话,可以使用 PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); 的方式,要记得在一轮操作做完后调用 flush() 方法清空缓冲区,不然会输出不了结果。

如果你对我的代码感兴趣,你也可以参考一下 我的模板

文章作者: Inno Fang
文章链接: https://innofang.github.io/2018/03/05/记一次由Java读写速度引发的TLE的一点探索/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来自 Inno's Blog