#java #algorithm #performance #parsing
#java #алгоритм #Производительность #анализ
Вопрос:
У меня есть следующие данные в файле:
P1==1,P3==123d3213213345
P1==2,P2==123321512332456*
P1==3,P2==123321451232123332*,P4==9512*
P1==4,P3==312512343243234*,P4==98*, P5=453213264
Мне нужно сопоставить его со следующей структурой, которая имеет одну строку вышеуказанных данных в качестве входных данных.
private static class ReferenceData {
private int P1;
private String P2;
private String P3;
private String P4;
private String P5;
public ReferenceData(String line) {
//Parse and store in the corresponding class fields
}
}
Эта единая структура абсолютно критична для производительности моего приложения.
Что было бы самым быстрым (и я имею в виду действительно быстрый способ) для анализа и сохранения вышеупомянутой структуры в соответствующих полях класса?
Я выполнил свою домашнюю работу. Я тщательно профилировал код. Именно здесь находится узкое место. Это не IO или что-то еще. О! и еще одна вещь, переменные P1, P2 — их могут быть тысячи. Это всего лишь пример.
Примечание: я не могу использовать jni
Комментарии:
1. Что обозначают звездочки?
2. Кроме того, почему вы думаете, что синтаксический анализ будет узким местом … по сравнению с дисковым или сетевым вводом-выводом, я имею в виду…
3. Будет ли P4 присутствовать в файле несколько раз? В таком случае, какое значение P4 вы принимаете? Или P1 является драйвером для каждой строки?
4. Похоже, что выполнение двух простых разбиений на
,then==должно дать вам всю информацию, необходимую для заполнения вашего объекта.5. @rahul, все ли ваши файлы являются файлами csv?
Ответ №1:
Я написал парсер конечного автомата с ручным кодированием и простой тестовый тест. Для теста я также включил другие предлагаемые стратегии синтаксического анализа: разделение и регулярное выражение (обратите внимание, что они не работали так, как опубликовано, поэтому я внес некоторые исправления).
Некоторые примечания:
- Я использовал образцы данных, предоставленные оригинальным плакатом, но удалил лишний пробел и ошибочный символ «d». Я думаю, что «d» была ошибкой. При желании можно было бы добавить немного больше работы с пробелами для обработки.
- Избегал распределений, таких как оператор «new» или методы, которые создавали бы объекты.
- Удалось избежать вызова внешних методов — ценой некоторого повторения кода. (Примечание: все еще существует случай Integer.parseInt(), с которым можно было бы покончить, избегая внешнего вызова, а также получая более производительный синтаксический анализ).
Сначала результаты:
Warming up...
Benchmarking...
average parse time for SplitParser: 5154.4ns
average parse time for RegexParser: 1820.8ns
average parse time for StateMachineParser: 401.3ns
И вот код:
package test;
import java.text.ParseException;
import java.util.Arrays;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Parser {
private static final List<String> SAMPLE_INPUTS = Arrays.asList(
"P1==1,P3==1233213213345",
"P1==2,P2==123321512332456*",
"P1==3,P2==123321451232123332*,P4==9512*",
"P1==4,P3==312512343243234*,P4==98*,P5==453213264");
public static void main(String... args) {
//test(new StateMachineParser());
//test(new RegexParser());
//test(new SplitParser());
benchmark(Arrays.asList(new SplitParser(), new RegexParser(), new StateMachineParser()));
}
private static void test(ReferenceDataParser parser) {
for (String input : SAMPLE_INPUTS) {
try {
System.err.println(parser.parse(input));
}
catch(ParseException pe) {
System.err.println("Failed to parse: " input);
int offset = pe.getErrorOffset();
StringBuilder buf = new StringBuilder(" ");
for (int i = 0; i < offset; i ) {
buf.append(' ');
}
buf.append('^');
System.err.println(buf.toString());
pe.printStackTrace();
}
}
}
private static void benchmark(List<ReferenceDataParser> parsers) {
int warmupIters = 100 * 1000;
int iters = 1000 * 1000;
System.err.println("Warming up...");
for (ReferenceDataParser parser : parsers) {
try {
for (String input : SAMPLE_INPUTS) {
for (int i = 0; i < warmupIters; i ) {
parser.parse(input);
}
}
}
catch(Exception e) {
System.err.println("parser failed: " parser.getClass().getSimpleName());
}
}
System.err.println("Benchmarking...");
for (ReferenceDataParser parser : parsers) {
try {
long start = System.nanoTime();
for (String input : SAMPLE_INPUTS) {
for (int i = 0; i < iters; i ) {
parser.parse(input);
}
}
long elapsed = System.nanoTime() - start;
System.err.println(String.format("average parse time for %s: %.1fns",
parser.getClass().getSimpleName(), elapsed / (double) (iters * SAMPLE_INPUTS.size())));
}
catch(Exception e) {
System.err.println("parser failed: " parser.getClass().getSimpleName());
}
}
}
public static interface ReferenceDataParser {
public ReferenceData parse(String line) throws ParseException;
}
public static class ReferenceData {
private final int p1;
private final String p2;
private final String p3;
private final String p4;
private final String p5;
public ReferenceData(int p1, String p2, String p3, String p4, String p5) {
this.p1 = p1;
this.p2 = p2;
this.p3 = p3;
this.p4 = p4;
this.p5 = p5;
}
public String toString() {
return String.format("P1=%s,P2=%s,P3=%s,P4=%s,P5=%s", p1, p2, p3, p4, p5);
}
}
private static class SplitParser implements ReferenceDataParser {
public ReferenceData parse(String line) throws ParseException {
int p1 = 0;
String p2 = null;
String p3 = null;
String p4 = null;
String p5 = null;
String lineSplit[] = line.split(",");
for(int i = 0; i < lineSplit.length; i ) {
String value = lineSplit[i].split("==")[1];
if(lineSplit[i].startsWith("P1")) {
p1 = Integer.valueOf(value);
}
else if(lineSplit[i].startsWith("P2")) {
p2 = value;
}
else if(lineSplit[i].startsWith("P3")) {
p3 = value;
}
else if(lineSplit[i].startsWith("P4")) {
p4 = value;
}
else if(lineSplit[i].startsWith("P5")) {
p5 = value;
}
}
return new ReferenceData(p1, p2, p3, p4, p5);
}
}
private static class RegexParser implements ReferenceDataParser {
private static Pattern p = Pattern.compile(
"(?:P1==(\d ))(?:\s*,P2==([0-9*] ))?(?:\s*,P3==([0-9*] ))?(?:\s*,P4==([0-9*] ))?(?:\s*,P5==([0-9*] ))?");
public ReferenceData parse(String line) throws ParseException {
Matcher m = p.matcher(line);
if(!m.matches()) {
throw new ParseException(line, 0);
}
int p1 = Integer.parseInt(m.group(1));
String p2 = m.group(2);//note: this can be null is P2 is not part of the line
String p3 = m.group(3);
String p4 = m.group(4);
String p5 = m.group(5);
return new ReferenceData(p1, p2, p3, p4, p5);
}
}
private static class StateMachineParser implements ReferenceDataParser {
private static final int STATE_INITIAL_P = 0;
private static final int STATE_P = 1;
private static final int STATE_P_NUM = 2;
private static final int STATE_EQ1 = 3;
private static final int STATE_EQ2 = 4;
private static final int STATE_VALUE = 5;
public ReferenceData parse(String line) throws ParseException {
int p1 = 0;
String p2 = null;
String p3 = null;
String p4 = null;
String p5 = null;
int state = STATE_INITIAL_P;
int length = line.length();
int pNum = 0;
int valueStart = 0;
int valueEnd = 0;
for (int i = 0; i < length; i ) {
char c = line.charAt(i);
switch(state) {
case STATE_INITIAL_P:
case STATE_P:
if (c != 'P') {
throw new ParseException(line, i);
}
state = STATE_P_NUM;
break;
case STATE_P_NUM:
if (c < '1' || c > '5') {
throw new ParseException(line, i);
}
pNum = c - '0';
state = STATE_EQ1;
break;
case STATE_EQ1:
if (c != '=') {
throw new ParseException(line, i);
}
state = STATE_EQ2;
break;
case STATE_EQ2:
if (c != '=') {
throw new ParseException(line, i);
}
valueStart = valueEnd = i 1;
state = STATE_VALUE;
break;
case STATE_VALUE:
if ((c >= '0' amp;amp; c <= '9') || c == '*') {
valueEnd ;
}
else if (c == ',') {
if (valueStart == valueEnd) {
throw new ParseException(line, i);
}
switch(pNum) {
case 1:
if (p1 != 0) {
throw new ParseException(line, i);
}
p1 = Integer.parseInt(line.substring(valueStart, valueEnd));
break;
case 2:
if (p2 != null) {
throw new ParseException(line, i);
}
p2 = line.substring(valueStart, valueEnd);
break;
case 3:
if (p3 != null) {
throw new ParseException(line, i);
}
p3 = line.substring(valueStart, valueEnd);
break;
case 4:
if (p4 != null) {
throw new ParseException(line, i);
}
p4 = line.substring(valueStart, valueEnd);
break;
case 5:
if (p5 != null) {
throw new ParseException(line, i);
}
p5 = line.substring(valueStart, valueEnd);
break;
default:
// illegal P-number
throw new ParseException(line, i);
}
state = STATE_P;
}
break;
}
}
switch(state) {
case STATE_INITIAL_P:
case STATE_P:
case STATE_P_NUM:
case STATE_EQ1:
case STATE_EQ2:
// invalid end-states
throw new ParseException(line, length);
case STATE_VALUE:
// valid end-state; finish with last parsed value
if (valueStart == valueEnd) {
throw new ParseException(line, length);
}
switch(pNum) {
case 1:
if (p1 != 0) {
throw new ParseException(line, length);
}
p1 = Integer.parseInt(line.substring(valueStart, valueEnd));
break;
case 2:
if (p2 != null) {
throw new ParseException(line, length);
}
p2 = line.substring(valueStart, valueEnd);
break;
case 3:
if (p3 != null) {
throw new ParseException(line, length);
}
p3 = line.substring(valueStart, valueEnd);
break;
case 4:
if (p4 != null) {
throw new ParseException(line, length);
}
p4 = line.substring(valueStart, valueEnd);
break;
case 5:
if (p5 != null) {
throw new ParseException(line, length);
}
p5 = line.substring(valueStart, valueEnd);
break;
default:
// illegal P-number
throw new ParseException(line, length);
}
break;
default:
throw new RuntimeException("unknown state: " state);
}
return new ReferenceData(p1, p2, p3, p4, p5);
}
}
}
Ответ №2:
Самый быстрый способ сделать это — написать свой собственный анализатор на основе конечного автомата.
Комментарии:
1. Звучит примерно так. Знаете какой-нибудь хороший материал, чтобы научиться его писать?
2. @rahul вы можете проверить, как компилируются и анализируются регулярные выражения, это делается с помощью конечных автоматов
Ответ №3:
используя регулярное выражение и предполагая, что Ps всегда в порядке:
static Pattern p = Pattern.compile("(?:P1=(d*)),s*(?:P2=(.*?))?,s*(?:P3=(.*?))?,s*(?:P4=(.*?))?,s*(?:P5=(.*?))?");
public ReferenceData(String line) {
Matcher m = p.matcher(line);
if(m.match()){
P1 = Integer.parseInt(m.group(1));
P2 = m.group(2);//note: this can be null is P2 is not part of the line
P3 = m.group(3);
P4 = m.group(4);
P5 = m.group(5);
}
}
Комментарии:
1. Использование регулярных выражений намного медленнее, чем простое разбиение их на токены. Поймите, что я уже знаю, как его разобрать. Что мне нужно, так это самый быстрый способ сделать это.
2. вы составили его профиль? большая часть медлительности регулярных выражений связана с возвратом в большинстве реализаций
Ответ №4:
Я не уверен насчет скорости этого, но вы должны быть в состоянии использовать несколько простых разделений, чтобы делать то, что вам нужно, предполагая, что файл не может быть искажен и вам не нужно проверять наличие неправильных строк:
public ReferenceData(String line) {
String lineSplit[] = line.split(",");
for(int i = 0; i < lineSplit.length; i ) {
String value = lineSplit[i].split("==")[1];
if(lineSplit[i].equals("P1")) {
this.P1 = Integer.valueOf(value);
}
else if(lineSplit[i].equals("P2")) {
this.P2 = value;
}
else if(lineSplit[i].equals("P3")) {
this.P3 = value;
}
else if(lineSplit[i].equals("P4")) {
this.P4 = value;
}
else if(lineSplit[i].equals("P5")) {
this.P5 = value;
}
}
}