莫名其妙 TLE
继昨天一次由System.out.println() 引起的 MLE&TLE后，今天随机到一道快速选择的题(P1923)，又遇到相似的问题，写完快速排序后修改几行代码就得到快速选择的代码，本以为轻松解决问题，然后又莫名其妙的 TLE。
原始代码：
public static void main(String[] args) throws IOException { Scanner in = new Scanner(System.in);// 标准输入 int n = in.nextInt(); int k = in.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; ++i) { a[i] = in.nextInt(); } quickSelect(a, 0, n-1, k);// 快速选择 System.out.println(a[k]);// 标准输出 in.close(); }
第一次尝试结果：
举一反三
有了昨天 System.out.println() 造成MLE 的经验，很容易就想到是因为使用Scanner(System.in)标准输入性能低下造成的 TLE，于是进行改进。
// 使用 StreamTokenizer 替代Scanner in = newScanner(System.in); StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
最终代码：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class Main { // StreamTokenizer对象 public static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); // 由 Token获取 int public static int nextInt() throws IOException { in.nextToken();// 从输入流获取标记 return (int)in.nval;// 转化 } // 主函数 public static void main(String[] args) throws IOException { int n = nextInt();// 自编写的读取整数函数 int k = nextInt(); int[] a = new int[n]; for (int i = 0; i < n; ++i) { a[i] = nextInt(); } quickSelect(a, 0, n-1, k); System.out.println(a[k]); } }
最终结果：
总结
- 使用 Scanner(System.in) 进行标准输出时，性能较差，不适合频繁调用。
- 频繁输入调用使用 StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
- 类 java.io.StreamTokenizer 可以获取输入流并将其分析为Token(标记)，使用nextToken()方法读取下一个标记。
- 默认情况下，StreamTokenizer 认为下列内容是Token：字母、数字、除c和c++注释符号以外的其他符号。
- 使用 BufferedReader 创建 StreamTokenizer 对象以提高效率。
- 调用 nextToken() 方法从输入流中获取标记，调用 nextToken() 方法后，如果 Token 是字符串，可用String s = st.sval获取，如果是整数，可用int x = (int)st.nval获取。
