洛谷_使用StreamTokenizer优化输入（java）

之前刷了很长时间的 lc，在 lc 平台比较好的一点是只需要编写方法的片段，不需要编写整段代码。只是长时间刷 lc 有点枯燥，lc 的标签感觉分类不是特别准，还有长时间不写输入输出我都已经快忘记基础代码怎么写了 😂。所以今年开始我改在洛谷刷题了，也算换换口味嘛。

只是在提交了几题之后发现有点不对劲，有的题目我编写的算法时间复杂度和空间复杂度理应都是没有问题的，但是一提交就会内存超限？！！前前后后检查好多遍发现居然是输入类 Scanner 的问题，我想起大二刚开始学 java 语法的时候好像就只使用 Scanner 进行过输入，BufferReader 都是读文件的时候才用到。不过在洛谷提交发现，Scanner 的性能确实是很慢，数据量越多就越慢，一些简单的题目运行时间也会达到几百 ms 以上。

在这篇博客看了下原因：https://blog.csdn.net/linxdcn/article/details/72886231

Scanner 类性能差的原因主要还是它依赖正则表达式进行匹配，想象一下每次输入一个字符 Scanner 就需要匹配一次正则表达式，而 BufferReader 就是直接的读取字符到缓冲区，缓冲区填满了就再填充。

public class BufferedReader extends Reader {

  // 内部保存的Reader变量
  private Reader in;

  // 缓冲区
  private char cb[];

  // 默认缓冲区大小
  private static int defaultCharBufferSize = 8192;

  // 填充缓冲区的函数
  private void fill() throws IOException {
    int dst;

    // 省略了部分定位的代码

    int n;
    do {
      // 一次性读满缓冲区
      n = in.read(cb, dst, cb.length - dst);
    } while (n == 0);
    if (n > 0) {
      nChars = dst + n;
      nextChar = dst;
    }
  }

  // 读取一个字符
  public int read() throws IOException {
    synchronized (lock) {
      ensureOpen();
      for (;;) {
        if (nextChar >= nChars) {
          // 如果缓冲区读完了，填充
          fill();
          if (nextChar >= nChars) return -1;
        }
        if (skipLF) {
          skipLF = false;
          // 跳过换行符
          if (cb[nextChar] == '\n') {
            nextChar++;
            continue;
          }
        }
        return cb[nextChar++];
      }
    }
  }
}

public final class Scanner implements Iterator<String>, Closeable {

  // 缓冲区
  private CharBuffer buf;

  // 缓冲区大小1KB
  private static final int BUFFER_SIZE = 1024;

  public String nextLine() {
    // 如果缓冲中的下一次匹配是行匹配，则直接返回
    if (hasNextPattern == linePattern()) return getCachedResult();
    clearCaches();

    // 否则通过正则表达式匹配返回一行字符串
    String result = findWithinHorizon(linePattern, 0);
    if (result == null) throw new NoSuchElementException("No line found");
    MatchResult mr = this.match();
    String lineSep = mr.group(1);
    if (lineSep != null) result = result.substring(
      0,
      result.length() - lineSep.length()
    );
    if (result == null) throw new NoSuchElementException();
    else return result;
  }
}

（1）使用 StreamTokenizer 快速输入数字和字母

StreamTokenizer 也是输入类，不过它在输入数字和字母的处理上比 BufferReader 还要更快。不过它也只能接收数字或字母，如果输入除空格和回车以外的字符（如：!@#$%^&*()[]{})无法识别，会显示 null。

StreamTokenizer 可以获取输入流并根据空格和回车分割成 Token（标记），用 nextToken 方法读取下一个标记。如果标记是字符串，用 st.sval 获取标记，如果是数字用 st.nval 获取标记，st.navl 默认是 double 类型，读取整数的时候需要显式转型。

// 使用优化Java输入方式
class Input {

  StreamTokenizer streamTokenizer = new StreamTokenizer(
    new BufferedReader(new InputStreamReader(System.in))
  );

  public int nextInt() throws IOException {
    streamTokenizer.nextToken();
    return (int) streamTokenizer.nval;
  }

  public String nextString() throws IOException {
    streamTokenizer.nextToken();
    return streamTokenizer.sval;
  }
}

在洛谷实际测试中也发现，这种方式对性能的提升不是一点点，而是非常显著。比如下面这题，使用 Scanner 直接内存超限提交失败，仅仅换成 StreamTokenizer 之后内存马上变成之前的。

（2）使用 BufferReader 读取整行

刚才说到，StreamTokenizer 的硬伤就是不能识别特殊字符，这在处理字符串的时候就不灵活了，此时使用 BufferReader 是更佳选择。虽然说 Scanner 也是有 NextLine 方法，但是它还是会使用正则表达式匹配，性能还是差了一点。

BufferedReader inBuff=new BufferedReader(new InputStreamReader(System.in));
String s=inBuff.readLine()

（3）PrintWriter 快速输出

其实我主要还是使用System.out.println()输出的，不过在博客 https://www.cnblogs.com/wei-jing/p/10756609.html 看到有PrintWriter的介绍，目前使用 sout 尚未遇到超时的情况，这里简单做下记录，以后遇到再更新：

import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class Test {

  public static void main(String[] args) {
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    String s = "hollow world";
    int i = 12344;
    out.print(s + " " + i);
    out.flush();
    /**
     * 输出内容
     * hollow world 12344
     */
  }
}