Chciałbym się podzielić moja ostatnią obserwacją dotyczącą wyrażeń regularnych w Pythonie. Przyzwyczajony do wysokiej wydajności tychże w Perlu założyłem, że Python radzi sobie z nimi równie dobrze, albo nawet lepiej. Niestety nie do końca tak jest.

Załóżmy że parsujemy dość długie linie (1k) np. takim wyrażeniem: /a*b/. Linie te zawierają tylko literę a, więc nie pasują do wyrażenia.

Program w Pythonie:

import re
from time import time
buf = 'a' * 1024
start = time()
i = 0;
while i < 1000:

i += 1
re.search("a*b", buf)

print time() - start

Program w Perlu:

use Time::HiRes qw(time);
my $buf = "a" x 1024;
my $start = time();
my $i = 0;
while ($i < 1000) {

$i += 1;
$buf =~ /a*b/;

}
print time() - $start;

Jaki będzie czas wykonania obu programów ?
perl = 0.0008 s
python = 1.203 s (1500 x wolniej !!)

Sytuacja jaką tutaj mamy to tzw. Catastrophic Backtracking. Podczas parsowania łańcucha zachłanne dopasowanie a* zabiera wszystkie znaki i dalej okazuje się, że nie da się dopasować litery b. Zatem oddaje jedną literę i ponownie sprawdza czy jest b, itd, aż stwierdzi, że nie da się bufora dopasować. Perl radzi sobie z tym wyjątkowo dobrze, ze względu na optymalizację polegającą na sprawdzeniu czy łańcuchy stałe z wyrażenia w ogóle występują w testowanym buforze. Tu stwierdza od razu, że litery b nie ma, więc nie podejmuje dalszych działań.

Aby sprawdzić jak Perl działa kiedy ta optymalizacja nie jest wykonywana, modyfikuję wyrażenie tak /a*[bc]/:
perl = 9.09 s
python = 9.13 s

Dla porządku wykonałem test, w którym udaje się dopasowanie, wyrażenie /a*[abc]/
perl = 0.001 s
python = 0.003 s

Prekompilowanie tych wyrażeń w Pythonie (Perl to robi automatycznie) nie przyniosło zauważalnej zmiany, pewnie dlatego, że były krótkie.

Pisząc regexpy w aplikacjach wymagających wysokiej wydajności, warto zadać sobie trud i sprawdzić jakie będą czasy wykonania dla różnych danych wejściowych. W moim przypadku zmieniałem wywołanie re.match na re.search, dla dość skomplikowanego wyrażenia. W tym pierwszym, łańcuchy, które nie pasowały były od razu eliminowane. Spodziewałem się spadku wydajności, ale nie 1500 razy – trafiłem w Catastrophic Backtracking.

Więcej o „katastrofie” i metodach radzenia sobie z tą sytuacją (tu większe możliwości ma Perl, obsługuje „Possessive Quantifiers” i „Atomic Grouping”):
http://www.regular-expressions.info/catastrophic.html
.

Testy wyrażeń regularnych (Perl, Python, Ruby):
http://snowplow.org/martin/rebench/
.

Tomasz Prus
Projektant Systemów Informatycznych