我的应用程序期望json请求包含一个(可能是多维的)未排序数组，该数组只有整数和可能的null值。类似[6, 2, [4, 3],[[[5], nil], 1]]
由于我无法解析无效的json，我不得不使用regex来做一些脏活，而且速度非常慢。
例如，上面的测试用例大约需要1.xx seconds才能完成，而具有10000元素的平面阵列所需的少于1 second
目前，我正在将请求正文作为字符串，然后应用正则表达式。
static ArrayList<Integer> getIntegers(String requestData) {
// Apply a regex to the request body
final String regularExpression = "([^\d])+";
// to get all the nested arrays
Pattern pattern = Pattern.compile(regularExpression);
String[] results = pattern.split(requestData);
ArrayList<Integer> numbers = new ArrayList<>();
// loop over the results and add to numbers array
for (String result : results) {
try {
numbers.add(Integer.valueOf(result));
} catch (NumberFormatException e) {
// Catch and skip any non integers
}
}
return numbers;
}
}
我有没有办法加快速度，或者有没有一种性能更好的替代方法？如果我需要处理一个包含20000个元素的多维数组，那就太慢了。
这个答案已经指向了正确的方向。第一个重要步骤是将昂贵的Pattern.compile操作移出该方法，因为Pattern实例可以重用。
此外，迭代匹配的数量可以避免创建split的数组。现在，您也可以跳过子String的创建：
static final Pattern NUMBER = Pattern.compile("\d+");
static ArrayList<Integer> getIntegers(String requestData) {
ArrayList<Integer> numbers = new ArrayList<>();
Matcher m = NUMBER.matcher(requestData);
while(m.find()) numbers.add(Integer.parseInt(requestData, m.start(), m.end(), 10));
return numbers;
}
Java 9中添加了CCD_ 9。如果你在旧版本上操作，你可以创建自己的变体。为了简化，现在只支持基数为10:
static final Pattern NUMBER = Pattern.compile("-?\d+");
static ArrayList<Integer> getIntegers(String requestData) {
ArrayList<Integer> numbers = new ArrayList<>();
Matcher m = NUMBER.matcher(requestData);
while(m.find()) numbers.add(parseInt(requestData, m.start(), m.end()));
return numbers;
}
static int parseInt(CharSequence cs, int start, int end) {
int pos = start;
if(pos >= end) throw format(cs, start, end);
boolean negative = cs.charAt(pos) == '-';
if((negative || cs.charAt(pos) == '+') && ++pos==end)
throw format(cs, start, end);
int value = 0;
for(; pos < end; pos++) {
int next = cs.charAt(pos) - '0';
if(next < 0 || next > 9) throw format(cs, start, end);
if(value < Integer.MIN_VALUE/10) throw size(cs, start, pos, end);
value = value * 10 - next;
}
if(value > 0 || !negative && value == Integer.MIN_VALUE)
throw size(cs, start, pos, end);
return negative? value: -value;
}
private static RuntimeException format(CharSequence cs, int start, int end) {
return start > end? new IndexOutOfBoundsException(end+" < "+start):
new NumberFormatException(start == end?
"empty string": cs.subSequence(start, end).toString());
}
private static RuntimeException size(CharSequence cs, int start, int pos, int end) {
for(; pos < end; pos++)
if(cs.charAt(pos) < '0' || cs.charAt(pos) > '9') return format(cs, start, end);
return new NumberFormatException(cs.subSequence(start, end)+" outside the int range");
}
我修改了一些，创建了以下类：
class JsonNumberParser {
private final String json;
private final int length;
private final List<Integer> result;
private final char[] buffer = new char[64];
private int bufferIndex = 0;
public JsonNumberParser(String json) {
this.json = json;
length = json.length();
result = new ArrayList<>(length);
}
public List<Integer> parse() {
char c;
for (int i = 0; i < length; i++) {
c = json.charAt(i);
// if we encounter a comma and the buffer contains data
if (c == ',' && bufferIndex > 0) {
// then we add the new number
addBuffer();
// and reset the buffer
while (bufferIndex > 0) {
buffer[--bufferIndex] = ' ';
}
} else if (c == '-' || (c >= '0' && c <= '9')) {
buffer[bufferIndex++] = c;
}
}
// add the last possible number, if there was any
if (bufferIndex > 0) {
addBuffer();
}
// return the result
return result;
}
private void addBuffer() {
result.add(Integer.valueOf(new String(buffer, 0, bufferIndex)));
}
}
当然，您可以将所有这些放在一个方法中，但在添加Integers时会出现一些代码重复。
这个解析器的工作方式是，它使用缓冲区来缓冲数字，直到我们遇到逗号。这样，我们就可以在json中有大数字(在这个实现中最多64位)。
您可以使用如下示例所示的方法：
List<Integer> integers = new JsonNumberParser(jsonRequest).parse();
关于性能，我预计这将比使用Regex快得多。但遗憾的是，我手头没有的基准设置
请记住，这不是一个验证器，所以json字符串：
[[,,,]}]只会产生一个空的List
(也许)改进：我思考并搜索了更多。以下是可以使性能更好的一些改进：
1。可以通过为buffer分配new int[64]来重置它，这会产生更多的垃圾，但最终可能会更快。
2.使用此处建议的答案可以改进对数字的解析。它只使用简单的旧数学，没有创建字符串和解析整数。
如果性能是您的情况中的问题，我认为流API将不是一个好的解决方案。
static ArrayList<Integer> getIntegers(String requestData) {
char[] charArray = requestData.toCharArray();
ArrayList<Integer> numbers = new ArrayList<>();
for(char c : charArray) {
if(Character.isDigit(c)) {
numbers.add(Integer.valueOf(c) - 48);
}
}
return numbers;
}
使用堆栈怎么样？
我们可以升级平衡支架的问题。
在迭代字符串时，如果字符是notBracket()，那么它应该是一个数字。不用说，您忽略了所有逗号。同时，它还将验证阵列结构。
这具有O(n)的摊余复杂性。
您可以通过解析正模式(例如d+)而不是负模式([^d]+)来获得更好的性能。
private static final Pattern NUMBER = Pattern.compile("\d+");
List<Integer> extractNumbersRegex(String str) throws IOException {
Matcher m = NUMBER.matcher(str);
ArrayList<Integer> numbers = new ArrayList<>();
while (m.find()) {
numbers.add(Integer.parseInt(m.group()));
}
return numbers;
}
这对于从字符串中提取是可以的，但对于大数据，可以切换到不依赖于正则表达式而是直接匹配字符的更高效的方法：
List<Integer> extractNumbersHandcoded(String str) throws IOException {
ArrayList<Integer> numbers = new ArrayList<>();
int start = 0;
while (start < str.length()) {
if (Character.isDigit(str.charAt(start))) {
break;
}
start++;
}
int bufferedInt = 0;
for (int i = start; i < str.length(); i++) {
char c = str.charAt(i);
if (Character.isDigit(c)) {
bufferedInt = bufferedInt * 10 + (c - '0');
} else {
numbers.add(bufferedInt);
bufferedInt = 0;
}
}
return numbers;
}
如果你的数据大到流式，你可以考虑使用Streamtokenizer:的解决方案
List<Integer> extractNumbersStreamTokenizer(String str) throws IOException {
StreamTokenizer s = new StreamTokenizer(new StringReader(str));
ArrayList<Integer> numbers = new ArrayList<>();
int token;
while ((token = s.nextToken()) != StreamTokenizer.TT_EOF) {
if (token == StreamTokenizer.TT_NUMBER) {
numbers.add((int) s.nval);
}
}
return numbers;
}
所有解决方案都假定数据只包含整数文字(而不是浮点文字)。