Есть ли более быстрый способ разобрать строку для допустимых целых чисел в Java? - PullRequest
0 голосов
/ 08 января 2019

Мое приложение ожидает json-запросы, содержащие (возможно многомерный) несортированный массив с только целыми числами и возможными нулевыми значениями. Что-то вроде [6, 2, [4, 3],[[[5], nil], 1]]

Поскольку я не могу разобрать недействительный json, мне пришлось прибегнуть к использованию регулярного выражения для грязной работы, и это очень медленно.

Например, приведенный выше тестовый пример занимает около 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 элементами, это будет слишком медленно.

Ответы [ 5 ]

0 голосов
/ 09 января 2019

Этот ответ уже указывает в правильном направлении. Первым важным шагом является удаление дорогостоящей операции 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;
}

Integer.parseInt(CharSequence s, int beginIndex, int endIndex, int radix) был добавлен в Java 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");
}
0 голосов
/ 09 января 2019

Я немного повозился и создал следующий класс:

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] = '\0';
                }
            } 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.

Способ работы этого синтаксического анализатора заключается в том, что он использует буфер для буферизации цифр, пока мы не встретим запятую. Таким образом, мы можем иметь большие числа (до 64 цифр в этой реализации) в json.

Вы можете использовать это, как показано в следующем примере:

List<Integer> integers = new JsonNumberParser(jsonRequest).parse();

Что касается производительности, я ожидаю, что это будет намного быстрее, чем при использовании Regex. Но, к сожалению, у меня нет настройки бенчмарка под рукой


Имейте в виду, что это не валидатор, поэтому строка json: [[,,,]}] просто выдаст пустое List


(Возможно) Улучшения : Я подумал и искал немного больше. Вот некоторые улучшения, которые могут улучшить производительность:

1. Можно просто сбросить buffer, присвоив ему new int[64], что приведет к большему количеству мусора, но в итоге может быть быстрее.

2. Синтаксический анализ числа можно улучшить, используя предложенный ответ здесь . Который использует просто старую математику и не создает строк и разбирает целые числа.

0 голосов
/ 09 января 2019

Как насчет использования стека?

Мы можем обновить сбалансированные брекеты проблема.

Во время итерации строки, если символ notBracket(), он должен быть числом. Излишне говорить, что вы игнорируете все запятые. Одновременно он также проверит структуру массива.

Амортизированная сложность O(n).

0 голосов
/ 09 января 2019

Вы можете повысить производительность, анализируя положительные шаблоны (например, \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;
}

Все решения предполагают, что данные содержат только целочисленные литералы (не плавающие литералы).

0 голосов
/ 08 января 2019

Если в вашем случае проблема заключается в производительности, я не думаю, что потоковое 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;
        }
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...