Плохая производительность / скорость регулярных выражений с нетерпением
Я наблюдал очень медленные времена выполнения с выражениями с несколькими взглядами.
Я предполагаю, что это связано с базовыми структурами данных, но это выглядит довольно экстремально, и мне интересно, если я делаю что-то не так или есть известные обходные пути.
Проблема в том, чтобы определить, присутствует ли набор слов в строке в любом порядке. Например, мы хотим выяснить, находятся ли два термина "term1" И "term2" где-нибудь в строке. Я делаю это с выражением:
(?=.*\bterm1\b)(?=.*\bterm2\b)
Но я замечаю, что это на порядок медленнее, чем проверка сначала
\bterm1\b
и только тогда
\bterm2\b
Похоже, это указывает на то, что я должен использовать массив шаблонов вместо одного шаблона с предвидением... это правильно? это кажется неправильным...
Вот пример кода теста и полученное время:
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);
}
Это выводит в моем компьютере:
1754
150
3 ответа
Это может побрить время
жадный([AB]).*(?!\1)[AB]
нежадным([AB]).*?(?!\1)[AB]
переделывать
Я сделал свои собственные скамейки по этому вопросу. Соответствие одному члену за раз /term/
в отличие от двух терминов в одном регулярном выражении всегда будет занимать меньше времени, потому что это не
возвраты. Это так же просто, как strncmp (термин). И выполнение 2 условия отдельно будет тогда
намного быстрее.
Если вы можете определить термины так, чтобы не было возможности совпадения, то это
путь. то есть; /term1/ && /term2/.
Невозможно объединить термины в одно регулярное выражение, не вызывая возврат.
То есть, если вы действительно заботитесь о перекрытии, то есть методы, чтобы минимизировать
возвраты.
/(?=.*A)(?=.*B)/ аналогично /A/ && /B/, за исключением того, что кажется, что он намного медленнее и не учитывает перекрытия.
Итак, если вы действительно заботитесь о перекрытии (и я настоятельно рекомендую это сделать), есть
два способа, которые могут быть объединены для максимальной эффективности.
/ (A | B). * (?! \ 1) (?: A | B) /
или же
/A/ && /B/ && /(A|B) .* (?!\1)(?:A|B)/
Этот последний добавит небольшие (относительные) издержки, но может заблокировать доступ в логике
цепь, требующая, чтобы A и B по крайней мере существовали, перед проверкой на перекрытие.
И, в зависимости от того, где A и B существуют в строке, /(A|B) .* (?!\1)(?:A|B)/
может занять некоторое время, но это все еще самый короткий путь, когда есть все
в среднем.
Ниже приведена программа на Perl, которая сравнивает некоторые примерные (возможные сценарии) строки.
Удачи!
use strict;
use warnings;
use Benchmark ':hireswallclock';
my ($t0,$t1);
my ($term1, $term2) = ('term','m2a');
my @samples = (
' xaaaaaaa term2ater ',
' xaaaaaaa term2aterm ',
' xaaaaaaa ter2ater ',
' Aaa term2ater ' . 'x 'x100 . 'xaaaaaaa mta ',
' Baa term ' . 'x 'x100 . 'xaaaaaaa mta ',
' Caa m2a ' . 'x 'x100 . 'xaaaaaaa term ',
' Daa term2a ' . 'x 'x100 . 'xaaaaaaa term ',
);
my $rxA = qr/$term1/;
my $rxB = qr/$term2/;
my $rxAB = qr/ ($term1|$term2) .* (?!\1)(?:$term1|$term2) /x;
for (@samples)
{
printf "Checking string: '%.40s'\n-------------\n", $_;
if (/$term1/ && /$term2/ ) {
print " Found possible candidates (A && B)\n";
}
if (/ ($term1|$term2) .* ((?!\1)(?:$term1|$term2)) /x) {
print " Found non-overlaped terms: '$1' '$2'\n";
}
else {
print " No (A|B) .* (?!\\1)(A|B) terms found!\n";
}
print "\n Bench\n";
$t0 = new Benchmark;
for my $cnt (1 .. 500_000) {
/$rxA/ && /$rxB/;
}
$t1 = new Benchmark;
print " $rxA && $rxB\n -took: ", timestr(timediff($t1, $t0)), "\n\n";
$t0 = new Benchmark;
for my $cnt (1 .. 500_000) {
/$rxAB/;
}
$t1 = new Benchmark;
print " $rxAB\n -took: ", timestr(timediff($t1, $t0)), "\n\n";
$t0 = new Benchmark;
for my $cnt (1 .. 500_000) {
/$rxA/ && /$rxB/ && /$rxAB/;
}
$t1 = new Benchmark;
print " $rxA && $rxB &&\n $rxAB\n -took: ", timestr(timediff($t1, $t0)), "\n\n";
}
Выход
Checking string: ' xaaaaaaa term2ater '
-------------
Found possible candidates (A && B)
No (A|B) .* (?!\1)(A|B) terms found!
Bench
(?-xism:term) && (?-xism:m2a)
-took: 1.46875 wallclock secs ( 1.47 usr + 0.00 sys = 1.47 CPU)
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 3.3748 wallclock secs ( 3.34 usr + 0.00 sys = 3.34 CPU)
(?-xism:term) && (?-xism:m2a) &&
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 5.0623 wallclock secs ( 5.06 usr + 0.00 sys = 5.06 CPU)
Checking string: ' xaaaaaaa term2aterm '
-------------
Found possible candidates (A && B)
Found non-overlaped terms: 'm2a' 'term'
Bench
(?-xism:term) && (?-xism:m2a)
-took: 1.48403 wallclock secs ( 1.49 usr + 0.00 sys = 1.49 CPU)
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 3.89044 wallclock secs ( 3.89 usr + 0.00 sys = 3.89 CPU)
(?-xism:term) && (?-xism:m2a) &&
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 5.40607 wallclock secs ( 5.38 usr + 0.00 sys = 5.38 CPU)
Checking string: ' xaaaaaaa ter2ater '
-------------
No (A|B) .* (?!\1)(A|B) terms found!
Bench
(?-xism:term) && (?-xism:m2a)
-took: 0.765321 wallclock secs ( 0.77 usr + 0.00 sys = 0.77 CPU)
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 1.29674 wallclock secs ( 1.30 usr + 0.00 sys = 1.30 CPU)
(?-xism:term) && (?-xism:m2a) &&
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 0.874842 wallclock secs ( 0.88 usr + 0.00 sys = 0.88 CPU)
Checking string: ' Aaa term2ater x x x x x x x x x x x x x'
-------------
Found possible candidates (A && B)
No (A|B) .* (?!\1)(A|B) terms found!
Bench
(?-xism:term) && (?-xism:m2a)
-took: 1.46842 wallclock secs ( 1.47 usr + 0.00 sys = 1.47 CPU)
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 28.078 wallclock secs (28.08 usr + 0.00 sys = 28.08 CPU)
(?-xism:term) && (?-xism:m2a) &&
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 29.4531 wallclock secs (29.45 usr + 0.00 sys = 29.45 CPU)
Checking string: ' Baa term x x x x x x x x x x x x x'
-------------
No (A|B) .* (?!\1)(A|B) terms found!
Bench
(?-xism:term) && (?-xism:m2a)
-took: 1.68716 wallclock secs ( 1.69 usr + 0.00 sys = 1.69 CPU)
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 15.1563 wallclock secs (15.16 usr + 0.00 sys = 15.16 CPU)
(?-xism:term) && (?-xism:m2a) &&
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 1.64033 wallclock secs ( 1.64 usr + 0.00 sys = 1.64 CPU)
Checking string: ' Caa m2a x x x x x x x x x x x x x'
-------------
Found possible candidates (A && B)
Found non-overlaped terms: 'm2a' 'term'
Bench
(?-xism:term) && (?-xism:m2a)
-took: 1.62448 wallclock secs ( 1.63 usr + 0.00 sys = 1.63 CPU)
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 3.0154 wallclock secs ( 3.02 usr + 0.00 sys = 3.02 CPU)
(?-xism:term) && (?-xism:m2a) &&
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 4.56226 wallclock secs ( 4.56 usr + 0.00 sys = 4.56 CPU)
Checking string: ' Daa term2a x x x x x x x x x x x '
-------------
Found possible candidates (A && B)
Found non-overlaped terms: 'm2a' 'term'
Bench
(?-xism:term) && (?-xism:m2a)
-took: 1.45252 wallclock secs ( 1.45 usr + 0.00 sys = 1.45 CPU)
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 16.1404 wallclock secs (16.14 usr + 0.00 sys = 16.14 CPU)
(?-xism:term) && (?-xism:m2a) &&
(?x-ism: (term|m2a) .* (?!\1)(?:term|m2a) )
-took: 17.6719 wallclock secs (17.67 usr + 0.00 sys = 17.67 CPU)
Вам нужно поместить каждый цикл в отдельный метод, если поменять местами порядок тестов, вы получите разные результаты.
Можете ли вы сравнить это с test.indexOf('A') >= 0 && test.indexOf('B') >= 0 как я представляю это может быть намного быстрее?
Регулярное выражение вы разместили
(?=.\A\b)(?=.\B\b)
Не совпадает с тем, что в коде
.(?=.*B)(?=.*A)
На самом деле, первое регулярное выражение - это то, что не может сравниться с этим.
Можете ли вы привести некоторые примеры того, что должно соответствовать, а что нет.
Это регулярное выражение из объясненного кода.
Match any single character that is not a line break character «.»
Assert that the regex below can be matched, starting at this position (positive lookahead) «(?=.*B)»
Match any single character that is not a line break character «.*»
Between zero and unlimited times, as many times as possible, giving back as needed (greedy) «*»
Match the character “B” literally «B»
Assert that the regex below can be matched, starting at this position (positive lookahead) «(?=.*A)»
Match any single character that is not a line break character «.*»
Between zero and unlimited times, as many times as possible, giving back as needed (greedy) «*»
Match the character “A” literally «A»