1

Есть коллекция строк List<String> data = new ArrayList<>(); в ней хранятся строки такого плана:

book="book-1" operation="SELL" price="100.50" volume="81"  orderId="1"

Нужно получить все значения в кавычках я делаю это так:

private String getOrderParam(String line, String param) {
    String[] orderArr = line.split(param);
    return orderArr[1].split("\"")[0];
}

То есть сначала режу строку напополам так что-бы нужное значение оказалось под первым индексом, а потом еще раз отрезаю с кавычками с права от нужной мне части строки. Но все это очень медленно. Я заполняю массив String[] result = new String[5]; с первого параметра из строки до последнего, каждый раз вызывая этот метод.

Нужно что-бы метод возвращал массив строк, и при этом делал это максимально быстро до 5 секунд, коллекция data большая - 3 млн объектов. Данные я использую для создания объекта Order с полями : book, operation, price, volume, orderId Буду признателен за идеи, или код как добиться высокой производительности в решении задачи.

4
  • 2
    Неплохо бы пояснить, что для вас "быстро", а что "медленно", и дать оценку количества строк, раз вопрос о производительности. Это обработка потоковых данных или есть оффлайн набор строк в виде файла или коллекции? Запрашиваются всегда все поля или конкретное? Каждая строка обрабатывается один раз или произвольное количество?
    – Nofate
    8 мар 2017 в 23:07
  • 1
    Если запросов вида "верни параметр X в строке Y" много, сначала стоит распарсить строку в объект, с полями book, operation и т. д. и подумать в какую структуру данных их сложить.
    – Nofate
    8 мар 2017 в 23:09
  • @Nofate Да я собственно и парсю из в объекты с полями. Данных примерно 3 млн строк, быстро - среднее время 5 сек
    – Pavel
    9 мар 2017 в 0:06
  • А почему бы не заюзать регулярные выражения? 10 мар 2017 в 15:48

4 ответа 4

12

Для разбора строки достаточно один раз пройтись по ней слева направо конечным автоматом.

  1. Начинаем с состояния "Свойство".
  2. Собираем читаемые символы во временный буфер.
  3. По знаку =, если сейчас состояние "Свойство", забираем имя свойства из буфера в переменную, переходим в состояние "Значение", очищаем буфер.
  4. В состоянии "Значение" собираем читаемые символы в буфер.
  5. По закрывающей кавычке, забираем значение в переменную, очищаем буфер, сохраняем пару свойство-значение в поле объекта или HashMap, переходим в состояние "Свойство".
  6. При неожиданном для текущего состояния вводе кидаем исключение.

PS. Если внутри значений могут быть кавычки продумываем экранирование.


С другой стороны, пока ничего не известно про требования к скорости и о характере данных, я бы просто делал так:

Map<String, String> bookInfo = new HashMap();
String src = "book=\"book-1\" operation=\"SELL\" price=\"100.50\" volume=\"81\"  orderId=\"1\"";
for (String chunk : src.split("\" \"")) {
    String[] pair = chunk.split("=");
    bookInfo.put(pair[0], pair[1]);
}
2
  • Известно что данных очень много 3 млн. строк в коллекции. Про скорость что не должна превышать 5 сек.
    – Pavel
    9 мар 2017 в 0:01
  • Уточнил вопрос, прошу прощения за не точную формулировку.
    – Pavel
    9 мар 2017 в 0:10
6

Мне кажется стоит привести пример конечного автомата (по мотивам ответа Nofate)

Допускаем, что пары разделяются одним пробелом, внутри значений нет кавычек и прочая. Т.е. рассматриваем самый простой вариант без неожиданностей.

    String src = "book=\"book-1\" operation=\"SELL\" price=\"100.50\" volume=\"81\" orderId=\"1\"";
    src += " ";
    char[] charArr = src.toCharArray();
    boolean isKey = true;
    String key = "";
    String value = "";
    for (char c : charArr) {
        switch (c) {
            case '"':
                break;
            case '=':
                isKey = false;
                break;
            case ' ':
                isKey = true;
                System.out.println(key + ":" + value); //Выводим пару
                key = "";
                value = "";
                break;
            default:
                if (isKey) key += c;
                else value += c;
        }
    }

По просьбам трудящихся, оттюненая на скорую руку версия. Скорость выполнения на офисном ПК на 3.000.000 строк +/-3 секунды:

public class Main {
    public static void main(String[] args) {
        Map<String, String> out = new HashMap<>();
        String[] input = new String[3000000];
        for (int i = 0; i < 3000000; i++) {
            input[i] = "book=\"book-" + Math.random() + "\" operation=\"SELL\" price=\"" + Math.random() + "\" volume=\"" + Math.random() + "\" orderId=\"" + Math.random() + "\"";
        }
        long startTime = System.currentTimeMillis();
        for (String src : input) {
            char[] buffer = new char[30];
            char[] charArr = src.toCharArray();
            String key = "";
            int i = 0;
            for (char c : charArr) {
                if (c == '"') continue;
                if (c == '=') {
                    key = String.valueOf(buffer).trim();
                    buffer = new char[30];
                    i = 0;
                    continue;
                }
                if (c == ' ') {
                    out.put(key, (new String(buffer)).trim());
                    new String(buffer);
                    buffer = new char[30];
                    i = 0;
                    continue;
                }
                buffer[i++] = c;
            }
            out.put(key, (new String(buffer)).trim());
        }
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println(elapsedTime);
        System.out.println(out.size());
    }
}
3
  • 2
    Так ведь конкатенация строк - самый простой способ "убить" производительность.
    – Regent
    9 мар 2017 в 10:41
  • 1
    @Regent это максимально упрощенный пример, для общего понимания, как оно работает. Никто не мешает в качестве буфера использовать все что вам заблагорассудится.
    – rjhdby
    9 мар 2017 в 10:44
  • 1
    Да я-то воспользуюсь тем чем мне надо. Речь ведь про автора и про его 3 миллиона строк. Это, на мой взгляд, достаточное количество для мыслей об оптимизации. Замеров я не проводил, но есть подозрение, что даже с короткими строками возникнут проблемы при таком их количестве.
    – Regent
    9 мар 2017 в 10:53
1

Упоротое решение за один проход

package me.etki.perfground;

import java.util.LinkedList;
import java.util.List;

/**
 * @author Etki {@literal <[email protected]>}
 */
public class StringParser {

    enum State {

        EXTERIOR {
            @Override
            public State next(char c) {
                return c == ' ' ? EXTERIOR : KEY;
            }

            @Override
            public boolean expects(char c) {
                return c != '"' && c != '=';
            }
        },
        KEY {
            @Override
            public State next(char c) {
                return c == '=' ? EQUALITY_SIGN : KEY;
            }

            @Override
            public boolean expects(char c) {
                 return c != '"';
            }
        },
        EQUALITY_SIGN {
            @Override
            public State next(char c) {
                return OPENING_QUOTE;
            }

            @Override
            public boolean expects(char c) {
                return c == '"';
            }
        },
        OPENING_QUOTE {
            @Override
            public State next(char c) {
                return c == '"' ? CLOSING_QUOTE : VALUE;
            }
        },
        VALUE {
            @Override
            public State next(char c) {
                return c == '"' ? CLOSING_QUOTE : VALUE;
            }
        },
        CLOSING_QUOTE {
            @Override
            public State next(char c) {
                return c == ' ' ? EXTERIOR : KEY;
            }

            @Override
            public boolean expects(char c) {
                return c != '=' && c != '"';
            }
        };

        public State next(char c) {
            throw new UnsupportedOperationException("Somebody has forgotten to implement something");
        }

        public boolean expects(char c) {
            return true;
        }
    }

    public static class Tuple {
        private final CharSequence key;
        private final CharSequence value;

        public Tuple(CharSequence key, CharSequence value) {
            this.key = key;
            this.value = value;
        }

        public CharSequence getKey() {
            return key;
        }

        public CharSequence getValue() {
            return value;
        }
    }

    public static class Region implements CharSequence {
        private final CharSequence parent;
        private final int start;
        private final int end;

        public Region(CharSequence parent, int start, int end) {
            this.parent = parent;
            this.start = start;
            this.end = end;
        }

        @Override
        public int length() {
            return end - start;
        }

        @Override
        public char charAt(int index) {
            return parent.charAt(start + index);
        }

        @Override
        public CharSequence subSequence(int start, int end) {
            if (end > length()) {
                throw new IndexOutOfBoundsException();
            }
            return parent.subSequence(this.start + start, this.start + end);
        }

        @Override
        public String toString() {
            return parent.subSequence(start, end).toString();
        }
    }

    public static List<Tuple> parse(CharSequence input) {
        State state = State.EXTERIOR;
        List<Tuple> result = new LinkedList<>();
        int mark = -1;
        CharSequence key = null;
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (!state.expects(c)) {
                String s = "Provided string contains char " + c + " right after " + state + " state, and that's " +
                        "prohibited";
                throw new IllegalArgumentException(s);
            }
            State next = state.next(c);
            if (next.equals(state)) {
                continue;
            }
            if (next.equals(State.KEY) || next.equals(State.VALUE)) {
                mark = i;
            }
            if (state.equals(State.KEY)) {
                key = new Region(input, mark, i);
            } else if (state.equals(State.VALUE)) {
                result.add(new Tuple(key, new Region(input, mark, i)));
            }
            state = next;
        }
        return result;
    }
}

Которое благополучно не работает

// dummy - пустой метод, который берет аргумент и передает его в blackhole

# Run complete. Total time: 00:01:09

Benchmark                                                                                                   (input)   Mode  Samples          Score  Score error  Units
m.e.p.StringParserBenchmark.dummy            book="book-1" operation="SELL" price="100.50" volume="81"  orderId="1"  thrpt        1  316041178.489          NaN  ops/s
m.e.p.StringParserBenchmark.parse            book="book-1" operation="SELL" price="100.50" volume="81"  orderId="1"  thrpt        1    1084975.810          NaN  ops/s
m.e.p.StringParserBenchmark.warmThenParse    book="book-1" operation="SELL" price="100.50" volume="81"  orderId="1"  thrpt        1    1259713.331          NaN  ops/s

Если найду время выяснить в чем причина (почему у меня без создания новых строк и однократным проходом производительность находится на том же уровне, что у других примеров), то обновлю ответ.

update

Похоже, распределение методов по разным enum сильно не по нраву оптимизатору (и его можно понять - он не может спрогнозировать, какой метод будет вызван). Совсем чуть-чуть упоротости:

enum State {
    ...

    public static State next(char c, State current) {
        switch (current) {
            case EXTERIOR:
                return c == ' ' ? EXTERIOR : KEY;
            case KEY:
                return c == '=' ? EQUALITY_SIGN : KEY;
            case EQUALITY_SIGN:
                return OPENING_QUOTE;
            case OPENING_QUOTE:
                return c == '"' ? CLOSING_QUOTE : VALUE;
            case VALUE:
                return c == '"' ? CLOSING_QUOTE : VALUE;
            case CLOSING_QUOTE:
                return c == ' ' ? EXTERIOR : KEY;
            default:
                throw new IllegalStateException();
        }
    }

    public static boolean expects(char c, State current) {
        switch (current) {
            case EXTERIOR:
                return c != '"' && c != '=';
            case KEY:
                return c != '"';
            case EQUALITY_SIGN:
                return c == '"';
            case OPENING_QUOTE:
                return true;
            case VALUE:
                return true;
            case CLOSING_QUOTE:
                return c != '=' && c != '"';
            default:
                throw new IllegalStateException();
        }
    }
}

практически удваивает скорость работы:

Benchmark                                                                                                      (input)   Mode  Samples          Score  Score error  Units
m.e.p.StringParserBenchmark.dummy               book="book-1" operation="SELL" price="100.50" volume="81"  orderId="1"  thrpt        1  319058428.945          NaN  ops/s
m.e.p.StringParserBenchmark.parse               book="book-1" operation="SELL" price="100.50" volume="81"  orderId="1"  thrpt        1    1176753.244          NaN  ops/s
m.e.p.StringParserBenchmark.warmThenAltParse    book="book-1" operation="SELL" price="100.50" volume="81"  orderId="1"  thrpt        1    2057734.054          NaN  ops/s
m.e.p.StringParserBenchmark.warmThenParse       book="book-1" operation="SELL" price="100.50" volume="81"  orderId="1"  thrpt        1    1112356.422          NaN  ops/s
2
  • Как это вызывается?
    – Pavel
    10 мар 2017 в 19:26
  • 1
    @Павел StringParser.parse()
    – etki
    10 мар 2017 в 21:02
1

Возможен и такой вариант, по скорости не сильно отличается.

    Pattern p = Pattern.compile("\"(.*?)\""); 
    for (String src : input) {
        Matcher m = p.matcher(src);
        int i = 1;
        while (m.find()) {
            switch (i) {
                case 1: out.put("book", m.group());
                case 2: out.put("operation", m.group());
                case 3: out.put("price", m.group());
                case 4: out.put("volume", m.group());
                case 5: out.put("orderId", m.group());
            }
            i++;
        }
    }

ps: вкралась ошибка int i = 0; а надо =1 (или case сделать с нуля)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.