莫名其妙 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() 方法清空缓冲区，不然会输出不了结果。
- 最后记得关闭输入输出流，养成一个好习惯，这样即使忘记清空缓冲区，也会因为关闭输出流而自动清空缓冲区。
