sOlOHsU's Blogβ

灯火阑珊处

使用Java快速处理大数据量的输入

这里以读取int类型的数据为例。

Scanner

直接使用nextInt()

虽然是最方便的，但是也是最慢的。建议数据量小的时候使用。数据量大的情况下多半会超时。直接使用nextInt()方法的时候一般都会用BufferedInputStream封装一下输入流，速度能稍微快一些。

1
2
3
4
5
6
7
8
9
10

 Scanner scanner = new Scanner(new BufferedInputStream(System.in));

  long rows = scanner.nextLong();
  int cols = scanner.nextInt();

  for (int i = 0; i < rows * cols; i++) {
      int value = scanner.nextInt();
  }

  scanner.close();

使用next(), 然后手动Integer.parseInt()

这样能比直接使用nextInt()快不少，查看一下nextInt()的源码我们可以发现：nextInt()方法先用正则表达式从流中获取一个表示整型的字符串s，最后再返回Integer.parseInt(s)。多出的时间都消耗在进行模式匹配上了，这其实也就是直接使用nextInt()比较慢的原因之一。而如果我们事先知道输入的数据类型的话，就不用进行匹配，直接解析就可以了。

1
2
3
4
5
6
7
8
9
10

 Scanner scanner = new Scanner(new BufferedInputStream(System.in));

  long rows = Long.parseLong(scanner.next());
  int cols = Integer.parseInt(scanner.next());

  for (int i = 0; i < rows * cols; i++) {
      int value = Integer.parseInt(scanner.next());
  }

  scanner.close();

BufferedReader + StringTokenizer

使用BufferedReader按行读取，然后使用StringTokenizer获取每一行中使用空格符隔开的所有元素。速度甚至比C语言的scanf()还要快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tokenizer = new StringTokenizer("");

    tokenizer = new StringTokenizer(reader.readLine());
  long rows = Long.parseLong(tokenizer.nextToken());

  tokenizer = new StringTokenizer(reader.readLine());
  int cols = Integer.parseInt(tokenizer.nextToken());

    for (int i = 0; i < rows * cols; i++) {
      while (!tokenizer.hasMoreTokens()) {
          tokenizer = new StringTokenizer(reader.readLine());
      }
      int value = Integer.parseInt(tokenizer.nextToken());
  }

    reader.close();

实际测试结果

用以上三种方式从文件中读取10,000,000个int型数值所消耗的时间分别为 11.52秒，7.486秒，2.159秒。使用gcc的fscanf()所用时间为 5.303秒。

读取10,000,000个double型数值所消耗的时间分别为 41.125秒，16.082秒，9.271秒。使用gcc的fscanf()所用时间为 11.279秒。

总结

虽然使用BufferedReader和StringTokenizer处理输入可以获得让人满意的速度，但是需要写的代码相对来说是比较多的。在ACM比赛时可以准备一个工具类，比赛开始时，让一个人先把这个类写出来备用。

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

 /** Class for buffered reading int and double values */
  class Reader {
      static BufferedReader reader;
      static StringTokenizer tokenizer;
  
      /** call this method to initialize reader for InputStream */
      static void init(InputStream input) {
          reader = new BufferedReader(
                       new InputStreamReader(input) );
          tokenizer = new StringTokenizer("");
      }
  
      /** get next word */
      static String next() throws IOException {
          while ( ! tokenizer.hasMoreTokens() ) {
              //TODO add check for eof if necessary
              tokenizer = new StringTokenizer(
                     reader.readLine() );
          }
          return tokenizer.nextToken();
      }
  
      static int nextInt() throws IOException {
          return Integer.parseInt( next() );
      }
      
      static double nextDouble() throws IOException {
          return Double.parseDouble( next() );
      }
  }

参考资料