莫名其妙 MLE

  笔者并非ACM选手，但是由于最近备考 CCF 认证需要练练手，笔者是忠实的 Java 选手，于是就打算使用 Java 进行考试。随机到一道题P5461 赦免战俘，看题第一感觉就是递归处理，不出意外的成功写出了递归解法，然后高高兴兴的就在 OJ 上提交，然后就是莫名其妙的 MLE。

原始代码：

// 递归函数
public static void f(int[][] a, int x1, int x2, int y1, int y2) {
if (x2-x1==1 && y2-y1==1) {
a[x1][y1] = 0;
return;
} else {
for (int i = x1; i <= (x2-x1)/2+x1; ++i) {
for (int j = y1; j <= (y2-y1)/2+y1; ++j) {
a[i][j] = 0;
}
}
f(a, (x2-x1)/2+x1+1, x2, y1, (y2-y1)/2+y1);
f(a, x1, (x2-x1)/2+x1, (y2-y1)/2+y1+1, y2);
f(a, (x2-x1)/2+1+x1, x2, (y2-y1)/2+1+y1, y2);
}
}

第一次尝试结果：

第一次思考

  因为使用的是 int 类型的二维数组，而题目明确只需要存储 0 和 1。于是理所当然的想到将 int[ ][ ] 改为 byte[ ][ ]，于是进行第二次尝试。

第一次改进代码：

// 更改后的递归函数
public static void f(byte[][] a, int x1, int x2, int y1, int y2) {}

第二次尝试结果：

第二次思考

  第二次尝试仍然没有解决问题，证明问题不是出在那里，看来得另辟蹊径了。难道是递归深度太深导致爆内存？于是决定改进算法，仔细观察题目给出样例，发现数据有规律，类似于杨辉三角，数据依赖于该数上方和右上方的数(eg.a[2][3] = (a[1][3] + a[1][4]) % 2，也就是不进位的加法，可以使用异或优化计算，所以可以优化为 a[2][3] = a[1][3] ^ a[1][4])，于是将原有代码全部推倒从头再来，经过一番努力终于完成新算法，于是进行第三次尝试。

第二次改进代码：

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
byte[][] a = new byte[2048][2048];
n = (1<<n); // 等价于 n = Math.pow(2, n);
a[0][n+1] = 1;// 需要一个初始化数
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
// 等价于 a[i-1][j] = (a[i-1][j] + a[i-1][j+1]) % 2;
a[i][j] = (byte)(a[i-1][j] ^ a[i-1][j+1]);
System.out.printf("%d ", a[i][j]);
}
System.out.println();
}
in.close();
}
}

第三次尝试结果：

第三次思考

  如此简洁的代码怎么可能 MLE 呢？数组占用内存很小，计算使用位运算优化，没道理会 MLE，唯一可能的就是 IO 产生的内存占用了，于是开始测试自己的想法，每次输出完后调用 System.gc(); 处理一下垃圾。

第三次改进代码：

for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
a[i][j] = (byte)(a[i-1][j] ^ a[i-1][j+1]);
System.out.printf("%d ", a[i][j]);
}
System.out.println();
System.gc();// 测试是否 IO 引起的爆内存
}

第四次尝试结果：

第四次思考

  可以发现 MLE 的问题解决了，证明确实是IO 引起的爆内存，但是由于 System.gc(); 消耗时间太多又导致了 TLE，于是决定控制System.gc(); 先把题目 AC 了再说。但是经过多次调试都无法平衡时间和空间，要么TLE 要么 MLE。

第五次尝试结果：

第五次思考

  无法取巧通过测试，就只能另辟蹊径了，突然想到输出文件的时候都需要一个缓冲区，平时都没怎么注意这个问题，存在即合理，官方这么做必要有它的道理。于是查看源码以及搜集资料。
  发现 System.out.println(); 是一个同步方法，有一定的开销，在高并发的情况下，会严重影响性能，但这并不是主要问题。更多的是添加字符到缓冲区和打印的开销，这才是导致我的代码 MLE 的原因，因为我的代码每次只输出一个数字，而且产生很多次调用，产生极大开销。于是决定改用缓冲区暂存输出结果，最后输出结果。

使用 PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));代替 System.out.println();

最终代码：

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
int n = in.nextInt();
byte[][] a = new byte[2048][2048];
n = (1<<n);
a[0][n+1] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
a[i][j] = (byte)(a[i-1][j] ^ a[i-1][j+1]);
out.append(Byte.toString(a[i][j]));
out.append(" ");
}
out.append("\n");
}
out.flush();
out.close();
in.close();
}
}

最终结果：

总结

• 使用 System.out.println() 进行标准输出时，开销较大，不适合频繁调用。
• 同理，Scanner(System.in) 也不适合频繁调用(一次由 Scanner(System.in) 引起的 TLE)。
• 频繁输入调用使用 StreamTokenizer in = new      StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
• 频繁输出调用使用 PrintWriter out = new      PrintWriter(new BufferedOutputStream(System.out));
• 可手动调用 flush() 方法输出缓冲区，但是过于频繁的调用也有可能引发 TLE。
• 一般情况下，使用传统的System.out.println();我觉得足以应付，遇到频繁输出时再使用改进方法。当然为了防止输出问题导致TLE&MLE的话，可以直接使用PrintWriter out = new PrintWriter(new      BufferedOutputStream(System.out));记得在最后调用 flush() 方法清空缓冲区，不然会输出不了结果。
• 最后记得关闭输入输出流，养成一个好习惯，这样即使忘记清空缓冲区，也会因为关闭输出流而自动清空缓冲区。