首页 > 代码库 > Java端ACM输入解析器（高效）

Java端ACM输入解析器（高效）

2024-10-14 20:02:40   214人阅读

 最近注册了一个codeforeces的帐号，想在那上面刷刷题目。但是发现它用的是控制台输入数据。因此为了能够接收到这些数据，就动手写了一个Acm的输入解析器。

先说说这个解析器的缺点：

  • 这个解析器只能用于ascii码的输入，而由于acm一般为了照顾像c和c++这样的语言，都会选择使用ascii码作为输入，因此能完美符合这一限制。
  • 代码比较长，总共有300行代码。
  • 使用需要一定的缓存空间（约256字节）

再说说这个解析器的优点：

  • 速度较Scanner快不少。
  • 使用简单。
  • 功能强大。（对于ACM来说足够了）

速度较快是通过测试得到的，先说一下测试环境，在预热完毕的情况下，读取同样1000组数据，并循环读取100次，最后计算得到总的时间：

Test on parse integer:
AcmInputReader parse integer for 36527739ns
Scanner parse integer for 181622212ns
Test on parse integer:
AcmInputReader parse long for 46030367ns
Scanner parse long for 162285415ns
Test on parse double:
AcmInputReader parse double for 62484605ns
Scanner parse double for 675957938ns
Test on parse decimal:
AcmInputReader parse decimal for 64672405ns
Scanner parse decimal for 531412758ns

以上就是测试结果，可以看出对于解析整数，AcmInputReader比Scanner快了3倍将近，而解析浮点数则快了10倍，读入BigDecimal的速度也快了将近10倍。说一下做的性能优化：

  • 将整数x乘上10的运算以(x<<3)+(x<<1)代替。
  • 利用缓存机制将EOF作为普通字符处理，这样就可以不必每次都检查是否抵达文件尾。
  • 利用缓存机制分类ascii码字节代表的含义。
  • 减少了浮点数除法运算的发生。

下面是实际的代码，拷贝到自己提交的ACM文件中即可：

  1 /**
  2  * @author dalt
  3  * @since java1.7
  4  * @see java.lang.AutoCloseable 
  5  */
  6 class AcmInputReader implements AutoCloseable{
  7     private PushbackInputStream in;
  8 
  9     @Override
 10     public void close() throws IOException {
 11         in.close();
 12     }
 13 
 14     private static class AsciiMarksLazyHolder {
 15         public static final byte BLANK_MARK = 1;
 16         public static final byte SIGN_MARK = 1 << 1;
 17         public static final byte NUMERAL_MARK = 1 << 2;
 18         public static final byte UPPERCASE_LETTER_MARK = 1 << 3;
 19         public static final byte LOWERCASE_LETTER_MARK = 1 << 4;
 20         public static final byte LETTER_MARK = UPPERCASE_LETTER_MARK | LOWERCASE_LETTER_MARK;
 21         public static final byte EOF = 1 << 5;
 22         public static byte[] asciiMarks = new byte[256];
 23 
 24         static {
 25             for (int i = 0; i <= 32; i++) {
 26                 asciiMarks[i] = BLANK_MARK;
 27             }
 28             asciiMarks[‘+‘] = SIGN_MARK;
 29             asciiMarks[‘-‘] = SIGN_MARK;
 30             for (int i = ‘0‘; i <= ‘9‘; i++) {
 31                 asciiMarks[i] = NUMERAL_MARK;
 32             }
 33             for (int i = ‘a‘; i <= ‘z‘; i++) {
 34                 asciiMarks[i] = LOWERCASE_LETTER_MARK;
 35             }
 36             for (int i = ‘A‘; i <= ‘Z‘; i++) {
 37                 asciiMarks[i] = UPPERCASE_LETTER_MARK;
 38             }
 39             asciiMarks[0xff] = EOF;
 40         }
 41     }
 42 
 43     /**
 44      * 创建读取器
 45      *
 46      * @param input 输入流
 47      */
 48     public AcmInputReader(InputStream input) {
 49         in = new PushbackInputStream(new BufferedInputStream(input));
 50     }
 51 
 52     private int nextByte() throws IOException {
 53         return in.read() & 0xff;
 54     }
 55 
 56     /**
 57      * 如果下一个字节为b，则跳过该字节
 58      *
 59      * @param b 被跳过的字节值
 60      * @throws IOException if 输入流读取错误
 61      */
 62     public void skipByte(int b) throws IOException {
 63         int c;
 64         if ((c = nextByte()) != b) {
 65             in.unread(c);
 66         }
 67     }
 68 
 69     /**
 70      * 如果后续k个字节均为b，则跳过k个字节。这里{@literal k<times}
 71      *
 72      * @param b     被跳过的字节值
 73      * @param times 跳过次数，-1表示无穷
 74      * @throws IOException if 输入流读取错误
 75      */
 76     public void skipByte(int b, int times) throws IOException {
 77         int c;
 78         while ((c = nextByte()) == b && times > 0) {
 79             times--;
 80         }
 81         if (c != b) {
 82             in.unread(c);
 83         }
 84     }
 85 
 86     /**
 87      * 类似于{@link #skipByte(int, int)}, 但是会跳过中间出现的空白字符。
 88      *
 89      * @param b     被跳过的字节值
 90      * @param times 跳过次数，-1表示无穷
 91      * @throws IOException if 输入流读取错误
 92      */
 93     public void skipBlankAndByte(int b, int times) throws IOException {
 94         int c;
 95         skipBlank();
 96         while ((c = nextByte()) == b && times > 0) {
 97             times--;
 98             skipBlank();
 99         }
100         if (c != b) {
101             in.unread(c);
102         }
103     }
104 
105     /**
106      * 读取下一块不含空白字符的字符块
107      *
108      * @return 下一块不含空白字符的字符块
109      * @throws IOException if 输入流读取错误
110      */
111     public String nextBlock() throws IOException {
112         skipBlank();
113         StringBuilder sb = new StringBuilder();
114         int c = nextByte();
115         while (AsciiMarksLazyHolder.asciiMarks[c = nextByte()] != AsciiMarksLazyHolder.BLANK_MARK) {
116             sb.append((char) c);
117         }
118         in.unread(c);
119         return sb.toString();
120     }
121 
122     /**
123      * 跳过输入流中后续空白字符
124      *
125      * @throws IOException if 输入流读取错误
126      */
127     private void skipBlank() throws IOException {
128         int c;
129         while ((c = nextByte()) <= 32) ;
130         in.unread(c);
131     }
132 
133     /**
134      * 读取下一个整数（可正可负），这里没有对溢出做判断
135      *
136      * @return 下一个整数值
137      * @throws IOException if 输入流读取错误
138      */
139     public int nextInteger() throws IOException {
140         skipBlank();
141         int value = http://www.mamicode.com/0;
142         boolean positive = true;
143         int c = nextByte();
144         if (AsciiMarksLazyHolder.asciiMarks[c] == AsciiMarksLazyHolder.SIGN_MARK) {
145             positive = c == ‘+‘;
146         } else {
147             value = http://www.mamicode.com/‘0‘ - c;
148         }
149         c = nextByte();
150         while (AsciiMarksLazyHolder.asciiMarks[c] == AsciiMarksLazyHolder.NUMERAL_MARK) {
151             value = http://www.mamicode.com/(value << 3) + (value << 1) + ‘0‘ - c;
152             c = nextByte();
153         }
154 
155         in.unread(c);
156         return positive ? -value : value;
157     }
158 
159     /**
160      * 判断是否到了文件结尾
161      *
162      * @return true如果到了文件结尾，否则false
163      * @throws IOException if 输入流读取错误
164      */
165     public boolean isMeetEOF() throws IOException {
166         int c = nextByte();
167         if (AsciiMarksLazyHolder.asciiMarks[c] == AsciiMarksLazyHolder.EOF) {
168             return true;
169         }
170         in.unread(c);
171         return false;
172     }
173 
174     /**
175      * 判断是否在跳过空白字符后抵达文件结尾
176      *
177      * @return true如果到了文件结尾，否则false
178      * @throws IOException if 输入流读取错误
179      */
180     public boolean isMeetBlankAndEOF() throws IOException {
181         skipBlank();
182         int c = nextByte();
183         if (AsciiMarksLazyHolder.asciiMarks[c] == AsciiMarksLazyHolder.EOF) {
184             return true;
185         }
186         in.unread(c);
187         return false;
188     }
189 
190     /**
191      * 获取下一个用英文字母组成的单词
192      *
193      * @return 下一个用英文字母组成的单词
194      */
195     public String nextWord() throws IOException {
196         StringBuilder sb = new StringBuilder(16);
197         skipBlank();
198         int c;
199         while ((AsciiMarksLazyHolder.asciiMarks[(c = nextByte())] & AsciiMarksLazyHolder.LETTER_MARK) != 0) {
200             sb.append((char) c);
201         }
202         in.unread(c);
203         return sb.toString();
204     }
205 
206     /**
207      * 读取下一个长整数（可正可负），这里没有对溢出做判断
208      *
209      * @return 下一个长整数值
210      * @throws IOException if 输入流读取错误
211      */
212     public long nextLong() throws IOException {
213         skipBlank();
214         long value = http://www.mamicode.com/0;
215         boolean positive = true;
216         int c = nextByte();
217         if (AsciiMarksLazyHolder.asciiMarks[c] == AsciiMarksLazyHolder.SIGN_MARK) {
218             positive = c == ‘+‘;
219         } else {
220             value = http://www.mamicode.com/‘0‘ - c;
221         }
222         c = nextByte();
223         while (AsciiMarksLazyHolder.asciiMarks[c] == AsciiMarksLazyHolder.NUMERAL_MARK) {
224             value = http://www.mamicode.com/(value << 3) + (value << 1) + ‘0‘ - c;
225             c = nextByte();
226         }
227         in.unread(c);
228         return positive ? -value : value;
229     }
230 
231     /**
232      * 读取下一个浮点数（可正可负），浮点数是近似值
233      *
234      * @return 下一个浮点数值
235      * @throws IOException if 输入流读取错误
236      */
237     public float nextFloat() throws IOException {
238         return (float) nextDouble();
239     }
240 
241     /**
242      * 读取下一个浮点数（可正可负），浮点数是近似值
243      *
244      * @return 下一个浮点数值
245      * @throws IOException if 输入流读取错误
246      */
247     public double nextDouble() throws IOException {
248         skipBlank();
249         double value = http://www.mamicode.com/0;
250         boolean positive = true;
251         int c = nextByte();
252         if (AsciiMarksLazyHolder.asciiMarks[c] == AsciiMarksLazyHolder.SIGN_MARK) {
253             positive = c == ‘+‘;
254         } else {
255             value = http://www.mamicode.com/c - ‘0‘;
256         }
257         c = nextByte();
258         while (AsciiMarksLazyHolder.asciiMarks[c] == AsciiMarksLazyHolder.NUMERAL_MARK) {
259             value = http://www.mamicode.com/value * 10.0 + c - ‘0‘;
260             c = nextByte();
261         }
262 
263         if (c == ‘.‘) {
264             double littlePart = 0;
265             double base = 1;
266             c = nextByte();
267             while (AsciiMarksLazyHolder.asciiMarks[c] == AsciiMarksLazyHolder.NUMERAL_MARK) {
268                 littlePart = littlePart * 10.0 + c - ‘0‘;
269                 base *= 10.0;
270                 c = nextByte();
271             }
272             value += littlePart / base;
273         }
274         in.unread(c);
275         return positive ? value : -value;
276     }
277 
278     /**
279      * 读取下一个高精度数值
280      *
281      * @return 下一个高精度数值
282      * @throws IOException if 输入流读取错误
283      */
284     public BigDecimal nextDecimal() throws IOException {
285         skipBlank();
286         StringBuilder sb = new StringBuilder();
287         sb.append((char) nextByte());
288         int c = nextByte();
289         while (AsciiMarksLazyHolder.asciiMarks[c] == AsciiMarksLazyHolder.NUMERAL_MARK) {
290             sb.append((char) c);
291             c = nextByte();
292         }
293         if (c == ‘.‘) {
294             sb.append(‘.‘);
295             c = nextByte();
296             while (AsciiMarksLazyHolder.asciiMarks[c] == AsciiMarksLazyHolder.NUMERAL_MARK) {
297                 sb.append((char) c);
298                 c = nextByte();
299             }
300         }
301         in.unread(c);
302         return new BigDecimal(sb.toString());
303     }
304 }

我为了测试，在hdu上完成了题目1000（从控制台读入两个整数并输出其和，性能瓶颈为读入字符串和解析字符串），代码如下：

    public static void main(String[] args) throws Exception {
        AcmInputReader reader = new AcmInputReader(System.in);
        while (!reader.isMeetBlankAndEOF()) {
            System.out.println(reader.nextInteger() + reader.nextInteger());
        }
    }

执行结果为：

技术分享

其中前面三行都是我所提交的java代码，可以发现比其他选手所提交的java代码无论是执行时间还是执行时内存都要低上不少。但是相对来说代码长度就变得长了很多。需要清除代码长度不会过分影响java程序性能（除非永久代溢出），而真正影响java程序性能的实际上是内存和执行效率。无疑一般用Scanner的效率和所耗费的内存都比我所提供的AcmInputReader差不少。

可能有同学要问不是说整数解析的效率是Scanner的三倍吗，为什么执行效率只有快两倍。这是由于AcmInputReader有一个初始化的动作（自动发生），这个动作只执行一次并且永久有效，但是执行一次将会拖慢运行时间。也就是说在输入量足够大的时候，性能就有可能拉到三倍，而在输入量不足的时候，初始化带来的费用无法非常好地平摊，故平均速度将被肉眼可见地拖慢。

最后再稍微说一下AcmInputReader的用法：

先说明如何从输入流读取数据，假设输入流中有下列数据：

-412958 1842119

-59.9836 13541.84141 haDaweEqrj 1241jhjndjiqHUhie1^^%%$**123

-14129501.32681261951

下面是执行代码：

 1 AcmInputReader reader = new AcmInputReader(inputStream); //这里在绝大多数Acm的情况下inputStream均为System.in，即标准输入流。
 2 
 3 reader.nextInteger(); //读取下一个32位整数，这里返回-412958
 4 
 5 reader.nextLong(); //读取下一个64位整数，这里返回1842119
 6 
 7 reader.nextFloat(); //读取下一个单精度浮点数，这里返回-59.9836
 8 
 9 reader.nextDouble(); //读取下一个双精度浮点数，这里返回13541.84141
10 
11 reader.nextWord(); //读取下一个英文单词（大小写字母组成），这里返回haDaweEqrj 
12 
13 reader.nextBlock(); //读取下一块字符串（不含空白字符），这里返回1241jhjndjiqHUhie1^^%%$**123
14 
15 reader.nextDecimal(); //读取下一个高精度数值，这里返回-14129501.32681261951

 继续说明如何判断是否抵达输入流结尾：

reader.isMeetBlankAndEOF(); //返回true表示抵达输入流结尾，否则返回false。

最后说明如何跳过一些分隔字符，可能有些ACM题目以特殊字符分隔数据，比如逗号。下面假设输入为1134 , 1416

1 int num1 = reader.readInteger(); //读取1134
2 reader.skipBlankAndByte(‘,‘, 1); //跳过后续的1个逗号字符，以及出现的所有空白字符。（这里跳过了" , "）
3 int num2 = reader.readInteger(); //读取1416

上面就是完整的说明了，希望大家能喜欢我所提供的这个ACM输入解析的工具，也希望大家能在java端完美的解决所有可以被其它平台优雅解决的问题。

 

Java端ACM输入解析器（高效）


联系
我们