Schlechte Leistung/Geschwindigkeit von Regex mit Lookahead ⇐ Java

[Anonymous]

Ich habe extrem langsame Ausführungszeiten bei Ausdrücken mit mehreren Lookaheads beobachtet.

Ich nehme an, dass dies an den zugrunde liegenden Datenstrukturen liegt, aber es kommt mir ziemlich extrem vor und ich frage mich, ob ich etwas falsch mache oder ob es bekannte Problemumgehungen gibt.

Das Problem besteht darin, festzustellen, ob eine Reihe von Wörtern in beliebiger Reihenfolge in einer Zeichenfolge vorhanden sind. Wir möchten zum Beispiel herausfinden, ob zwei Begriffe „term1“ UND „term2“ irgendwo in einer Zeichenfolge stehen. Ich mache das mit dem Ausdruck:

Code: Select all

(?=.*\bterm1\b)(?=.*\bterm2\b)

Aber ich beobachte, dass dies um eine Größenordnung langsamer ist, als nur zuerst zu prüfen

Code: Select all

\bterm1\b

und genau dann

Code: Select all

\bterm2\b

Dies scheint darauf hinzudeuten, dass ich ein Array von Mustern anstelle eines einzelnen Musters mit Lookaheads verwenden sollte ... ist das richtig? es scheint falsch...

Hier ist ein Beispieltestcode und die daraus resultierenden Zeiten:

Code: Select all

public static void speedLookAhead() {
Matcher m, m1, m2;
boolean find;
int its = 1000000;

// create long non-matching string
char[] str = new char[2000];
for (int i = 0; i < str.length; i++) {
str[i] = 'x';
}
String test = str.toString();

// First method: use one expression with lookaheads
m = Pattern.compile("(?=.*\\bterm1\\b)(?=.*\\bterm2\\b)").matcher(test);
long time = System.currentTimeMillis();
;
for (int i = 0; i < its; i++) {
m.reset(test);
find = m.find();
}
time = System.currentTimeMillis() - time;
System.out.println(time);

// Second method: use two expressions and AND the results
m1 = Pattern.compile("\\bterm1\\b").matcher(test);
m2 = Pattern.compile("\\bterm2\\b").matcher(test);
time = System.currentTimeMillis();
;
for (int i = 0; i < its; i++) {
m1.reset(test);
m2.reset(test);
find = m1.find() && m2.find();
}
time = System.currentTimeMillis() - time;
System.out.println(time);
}

Dies gibt auf meinem Computer Folgendes aus:

Code: Select all

1754
150