背景: 远离 Scanner
今天无意翻阅 Scanner 类时，发现了一个很坑的地方：
// 摘抄自 Scanner JDK15 源码
public final class Scanner implements Iterator<String>, Closeable {
....
// Internal matcher used for finding delimiters
private Matcher matcher;
// Pattern used to delimit tokens
private Pattern delimPattern;
// Pattern found in last hasNext operation
private Pattern hasNextPattern;
private Pattern integerPattern;
private String digits = "0123456789abcdefghijklmnopqrstuvwxyz";
private String non0Digit = "[\\p{javaDigit}&&[^0]]";
private int SIMPLE_GROUP_INDEX = 5;
private String buildIntegerPatternString() {
String radixDigits = digits.substring(0, radix);
// \\p{javaDigit} is not guaranteed to be appropriate
// here but what can we do? The final authority will be
// whatever parse method is invoked, so ultimately the
// Scanner will do the right thing
String digit = "((?i)["+radixDigits+"\\p{javaDigit}])";
String groupedNumeral = "("+non0Digit+digit+"?"+digit+"?("+
groupSeparator+digit+digit+digit+")+)";
// digit++ is the possessive form which is necessary for reducing
// backtracking that would otherwise cause unacceptable performance
String numeral = "(("+ digit+"++)|"+groupedNumeral+")";
String javaStyleInteger = "([-+]?(" + numeral + "))";
String negativeInteger = negativePrefix + numeral + negativeSuffix;
String positiveInteger = positivePrefix + numeral + positiveSuffix;
return "("+ javaStyleInteger + ")|(" +
positiveInteger + ")|(" +
negativeInteger + ")";
}
private Pattern integerPattern() {
if (integerPattern == null) {
integerPattern = patternCache.forName(buildIntegerPatternString());
}
return integerPattern;
}
public int nextInt(int radix) {
// Check cached result
if ((typeCache != null) && (typeCache instanceof Integer)
&& this.radix == radix) {
int val = ((Integer)typeCache).intValue();
useTypeCache();
return val;
}
setRadix(radix);
clearCaches();
// Search for next int
try {
String s = next(integerPattern());
if (matcher.group(SIMPLE_GROUP_INDEX) == null)
s = processIntegerToken(s);
return Integer.parseInt(s, radix);
} catch (NumberFormatException nfe) {
position = matcher.start(); // don't skip bad token
throw new InputMismatchException(nfe.getMessage());
}
}
....
}
可见，Java 的 Scanner 是基于正则表达式实现的，这意味着 Scanner 的效率 相当低。如果在蓝桥杯之类的算法竞赛用 Scanner，会有很大一部分CPU时间会浪费在 Scanner 的正则解析上，就很可能跑出 TLE
这篇文章不探讨如何快速读取大型一般二进制文件，关注重点在于在低 JDK 版本下，如何快速解析文本，而非 “快速“ 读取文件。快速读取一般二进制大文件请考虑：
- 读取缓冲：使用直接缓冲 ByteBuffer.allocateDirect()
- 内存映射文件 FileChannel + MappedByteBuffer
认识 StringTokenizer
StringTokenizer 是一个自 Java 1.0 就被引入的类，用于以标识符分隔字符串，也就是解析文本
Scanner 之所以复杂，主要在于它假定所有输入数据都是任意的、类型是不确定的，同时 Scanner 还要兼顾处理输入流，所以不得不使用正则表达式去进行处理。
由于算法竞赛的给定数据的类型都是已知的，我们可以直接使用 StringTokenizer 去代替 Scanner
有报告显示，StringTokenizer 结合 BufferedReader 读入流的性能甚至高于 C 语言的 scanf()
构造方法
StringTokenizer 有三个常用构造方法
- 直接输入要解析的字符串，默认会把 “ \t\n\r\f” 当作分隔符。同时，解析返回结果不包含分隔符
Constructs a string tokenizer for the specified string. The tokenizer uses the default delimiter set, which is “ \t\n\r\f”: the space character, the tab character, the newline character, the carriage-return character, and the form-feed character. Delimiter characters themselves will not be treated as tokens.
Params: str – a string to be parsed.
Throws: NullPointerException – if str is null
public StringTokenizer(String str) {
this(str, " \t\n\r\f", false);
}
- 输入要解析的字符串和分隔符列表。解析返回结果不包含分隔符
Constructs a string tokenizer for the specified string. The characters in the delim argument are the delimiters for separating tokens. Delimiter characters themselves will not be treated as tokens.
Note that if delim is null, this constructor does not throw an exception. However, trying to invoke other methods on the resulting StringTokenizer may result in a NullPointerException.
Params: str – a string to be parsed.
delim – the delimiters.
Throws: NullPointerException – if str is null
public StringTokenizer(String str, String delim) {
this(str, delim, false);
}
- 输入要解析的字符串和分隔符列表。你决定要不要包含分隔符，true 为包含。
用法
获取每一段字符串 nextToken()
public String nextToken()
返回每一段被分隔的字符串 (token)，等效于 Scanner.next()， 返回结果是否包含分隔符取决于你的构造参数
如果没有更多 token，会抛出 java.util.NoSuchElementException
看看还有没有更多待分隔的字符串 hasMoreTokens()
public boolean hasMoreTokens()
true 表示有更多，可以安全地调用 nextToken()
增强 StringTokenizer
问题来了，StringTokenizer 好像并没有 Scanner 的 nextInt() nextLong() 之类的东西，怎么办？
现场写个类去解析他！
import java.util.StringTokenizer;
public class ExtendedStringTokenizer extends StringTokenizer {
public ExtendedStringTokenizer(String str) {
super(str);
}
public long nextLong() {
return Long.parseLong(this.nextToken());
}
public double nextDouble() {
return Double.parseDouble(this.nextToken());
}
public int nextInt() {
return Integer.parseInt(nextToken());
}
}
只需继承一下 StringTokenizer，寥寥几行代码便可搞定
注意：此处 nextInt() nextLong() 不允许输入为小数，否则会引发解析错误。如果确实需要处理小数，可以考虑在解析前使用 indexOf() 和 substring() 截去小数。
文件，以及有 EOF 的流快读方案
现在知道如何解析字符串了，但是怎么从流中读入字符串呢？
假设现在我们有了一个 InputStream inputStream，这个 InputStream 可以是：
- 标准输入
System.in - 文件
FileInputStream("FileName")
由于算法竞赛的 JDK 版本一般很低，无法使用 NIO
一次性全部读入
这是性能最好的，并且是典型的空间换时间的方案。
以蓝桥杯竞赛为例，通常提供高达 512 MB 的算法运行内存空间，这个时候可以直接把整个流全部读入后解析。
DataInputStream stream = new DataInputStream(inputStream);
ExtendedStringTokenizer tokenizer = new ExtendedStringTokenizer(new String(stream.readAllBytes()));
注： Java 1.7 以上可以使用 Files.readString(Path.of("filename")) 直接读入整个文件到字符串
为什么不直接使用 DataInputStream
有读者可能注意到了这里并没有直接使用 DataInputStream 提供的 readInt() readDouble() 等方法，这里有一点需要理解：
例如，下面代码：
ByteArrayInputStream byteArrayInputStream = new ByteArrayInputStream("5 1234567 2".getBytes());
DataInputStream dataInputStream = new DataInputStream(byteArrayInputStream);
System.out.println(dataInputStream.readLong());
System.out.println(dataInputStream.readLong());
System.out.println(dataInputStream.readLong());
输出：
3828113774942106934
Exception in thread "main" java.io.EOFException
根本不是我们想要的。
上面的说法是为了告诉你不要用它，事实上，更准确的说，readInt() readDouble() 是把一串二进制字节当作一个整体读入，用于处理二进制文件。与我们今天要做的事情（读取文本）一点关系都没有。
逐行读入
Reader 是专用于处理字符流的类，相对的，Stream 处理的是字节流
逐行读入时，使用 BufferedReader 包装 InputStreamReader， InputStreamReader 包装 InputStream 可以有效提升性能
// 注：BufferedReader 可以提供第二个参数，类型为 int，表示缓冲区容量，提供一个较大的容量可以更快
BufferedReader reader = new BufferedReader(new InputStreamReader(inputStream));
String line;
while ((line = reader.readLine()) != null) {
ExtendedStringTokenizer tokenizer = new ExtendedStringTokenizer(line);
// TODO: your code
}
如果读取目标是文件，可以用 new FileReader("filename") 代替 new InputStreamReader(inputStream)
由于 StringTokenizer 只是一个简单的小对象，所以循环反复创建的开销还是很小的。但还是比一次性读入慢了很多
不提供 EOF 的无限流快速方案
注意：
System.in标准输入流不一定不提供 EOF，若用户在终端上按下Ctrl+D或通过其他方式输入等效内容，则System.in会将此视作一个 EOF。但若用户一直不按Ctrl+D那就是无限等待输入了。
由于这种流不提供 EOF，我们没法直接全部读入，直接全部读入会造成永久阻塞。
但是，这种流肯定会告诉我们输入数据有多少行，我们可以用行数作为依据判断是否还要继续读。
假设第一行告诉我们后续输入有多少行：
// 注：BufferedReader 可以提供第二个参数，类型为 int，表示缓冲区容量，提供一个较大的容量可以更快
BufferedReader reader = new BufferedReader(new InputStreamReader(inputStream));
ExtendedStringTokenizer initTokenizer = new ExtendedStringTokenizer(reader.readLine());
int lineNum = initTokenizer.nextInt();
for (int i = 0; i < lineNum; i++) {
// TODO: your code
ExtendedStringTokenizer tokenizer = new ExtendedStringTokenizer(reader.readLine());
}
如果读取目标是文件，可以用 new FileReader("filename") 代替 new InputStreamReader(inputStream)
Reader 逐字符读取
如果输入数据，一个字符（注意不是字节）就是一个整体，那么还可以逐字符读取：
所用方法：
public int read()
读一个字符，并返回它。如果读到了 EOF 则返回 -1
例如：读取一个 ASCII 编码的、读取目标为数字、有换行符的文件到一个二维数组，每一个数字都是一个整体，每次换行就读取到数组的下一行。
var reader = new BufferedReader(new FileReader(PATH), 1 << 16);
byte[][] maze = new byte[100][100]; //读取的结果位于 0~9 之间，byte省空间
int lineCode = 0; // 也是实际有效行数
int colCode = 0; // 实际有效列数
int token;
while ((token = reader.read()) != -1) {
if (token >= '0' && token <= '9') {
maze[lineCode][colCode] = (byte) (token - '0');
colCode++;
} else if (token == '\n') {
lineCode++;
if (colCode == 0) {
colNum = colCode;
}
colCode = 0;
}
}
多个数字(字符)是一个整体
对于多个数字是一个整体的，当然也可以使用自行读取一组数据到缓冲区，然后自行解析。然而，编写解析代码所花费的时间可能远不如使用 StringTokenizer 划算，而且这样操作带来的性能提升实际上也非常有限。
所用 Reader 方法：
public int read()
public int read(char cbuf[], int off, int len) throws IOException
后者为：从流中读取指定长度(len)的字符流，并从偏移量(off)开始装入你的数组 cbuf[]，返回实际读取的有效长度（实际长度小于等于 len）
当然也可以使用前文提到的 DataInputStream
后记：一些常见误区
遍历字符串，不要 toCharArray() 后遍历
就我个人在 LeetCode 的刷题经验，当字符串编码为 Latin 时，直接 String.charAt() 会比 toCharArray() 后遍历更快（事实上在 JDK 源代码也可以找到相关依据）。
若对此有疑问，请阅读 toCharArray() 的源代码，并与 String.charAt() 进行对比，可见：
toCharArray()会创建一个新字符数组，然后逐字符拷贝，并与0xFF进行与运算，这比System.arraycopy()直接数组拷贝的性能低很多。- 尽管
charAt()也会进行一次与运算，但却不需要逐字拷贝而是直接访问 String 内部的字符数组。
