Perl (25) - Regulární výrazy - závěr

V posledním díle věnovaném regulárním výrazům se podíváme na měření rychlosti a debugging.

25.1.2006 06:00 | Jiří Václavík | přečteno 18733×

Porovnání rychlosti několika regulárních výrazů

Pro měření času potřebného pro vykonání určitého úseku kódu se v Perlu obvykle používá modul Benchmark. Nyní si ukážeme pouze to, jak pomocí něj porovnávat rychlosti regulárních výrazů. To ovšem není zdaleka jediné užití. Benchmark se používá poměrně často a někdy později v seriálu si podrobněji rozebereme i jeho jiné funkce. Modul Benchmark načteme takto:

use Benchmark qw(:all);

Nyní využijeme jen jeho jedinou funkci a to cmpthese. Ta se používá právě pro porovnávání rychlostí jednotlivých úseků kódu. Jako parametr jí jsou předávany 2 hodnoty:

  1. číslo - je-li záporné, znamená minimální počet sekund, po které testování poběží
  2. odkaz na hash, jehož každý prvek obsahuje nějaký úsek kódu - právě rychlosti těchto úseků jsou pak porovnávány

My si zkusíme dokázat, že použití závorek s pamatováním hodnoty uvnitř nich je časově náročnější než speciální syntaxe závorek, která si svůj obsah nepamatuje.

Nejprve se musíme konkrétně rozhodnout, které regulární výrazy budeme porovnávat. Jako ukázku si zvolíme například tyto:

my $re1 = qr/X(\w)/o;
my $re2 = qr/X(?:\w)/o;

Dále je třeba určit s čím se budou tyto regulární výrazy porovnávat. Protože testujeme pouze rychlost závorek, musí být jediným odlišným faktorem v regulárním výrazu právě závorky a vše ostatní musí být stejné. To platí i o řetězcích, které budeme se vzory porovnávat. V opačném případě by to mohlo ovlivňovat rychlost.

Nastavíme tedy parametry funkce cmpthese. Předáme jí hash, jehož klíči budou nějaké unikátní řetězce (jména porovnávaných úseků) a hodnotami anonymní podprogramy, v nichž probíhá test regulárního výrazu.

Testovaný úsek bude obsahovat určitý počet porovnání nějakého řetězce s regulárním výrazem. Proto musíme definovat řetězec a počet porovnání (obě tyto hodnoty budou pro testování obou regulárních výrazů stejné).

Jako řetězec, který bude srovnáván, definujeme podřetězec "X5 " uvnitř dvou stejných podřetězců.

my $okoli = "zxcvasdf" x 500;
my $text = $okoli . "X5 " . $okoli;

Nastavíme počet opakování:

my $pocet_opakovani = 1000;

Ještě nám zbývá zadat 1. argument - minimální počet sekund, po které porovnávání poběží:

my $delka_testu = -3;

A můžeme volat cmpthese:

cmpthese($delka_testu, {
    "s pamatovanim"  => sub {$text =~ m/$re1/ for 1 .. $pocet_opakovani;},
    "bez pamatovani" => sub {$text =~ m/$re2/ for 1 .. $pocet_opakovani;},
});

Po chvilce čekání program vytiskne výsledky ve formě tabulky, seřazené podle rychlostí vzestupně. Sloupec Rate udává hodnotu, kolikrát byl proveden daný úsek kódu (tj. 1000 porovnávání) za sekundu. Další sloupce ukazují relativní rozdíl rychlostí každé dvojice úseků v procentech. V našem případě je tato dvojice jediná (nebereme v potaz pořadí), protože jsme k porovnávání zadali pouze 2 úseky.

$ perl cmpthese
                Rate  s pamatovanim bez pamatovani
s pamatovanim  115/s             --           -31%
bez pamatovani 168/s            46%             --
$

Pokud si zkusíte pohrát se vstupním řetězcem (změna délky, pozicí apod.), zjistíte, že poměr rychlostí záleží i na dalších okolnostech a to dost výrazně. Vždy by ale mělo být rychlejší porovnávání bez pamatování.

Zpracování regulárních výrazů

Způsob, kterým se zpracovávají regulární výrazy můžeme kontrolovat. Ne že by se debugging používal masově, ale v případech, kdy potřebujeme opravit nějakou chybu v rozsáhlém regulárním výrazu a nemáme tušení, kde by mohla být, může pomoci. V Perlu máme možnost zapnout sledování překladu a následného vyhodnocování pomocí jedné z následujících direktiv. Direktiva

use re "debug";

zapíná debugging. Budou tak nalezeny a podrobně rozepsány všechny regulární výrazy. Lze užít také přehlednější variantu se zvýrazněním:

use re "debugcolor";

Zkusíme tímto způsobem otestovat nějaký jednoduchý úsek kódu.

use re "debugcolor";
"xy123456zzz" =~ /^xy\d{6}z*(1)$/;

Program jako obyčejně spustíme:

$ perl debug.pl

Objeví se výpis. My si vysvětlíme pouze to nejdůležitější z něj. Začneme tímto úsekem:

   1: BOL(2)
   2: EXACT <xy>(4)
   4: CURLY {6,6}(7)
   6:   DIGIT(0)
   7: STAR(10)
   8:   EXACT <z>(0)
  10: OPEN1(12)
  12:   EXACT <1>(14)
  14: CLOSE1(16)
  16: EOL(17)
  17: END(0)

Každá položka nebo skupina položek (můžeme jim říkat uzly) vyjadřuje nějakou část regulárního výrazu. Číslo na začátku každého řádku je id uzlu. Za každým uzlem je v závorce id následujícího uzlu.

BOL znamená prázdný řetězec na začátku řádku - tedy ^. EXACT je přesná shoda řetězce mezi < a > - v našem případě xy. Kvantifikátor {6} je převeden na obecnější zápis {6,6}. 6krát se opakuje vše odsazené - v našem případě jen uzel DIGIT, který označuje numerický znak. Pokračujeme přesným výskytem znaku s libovolným počtem opakování. Dále máme 1. otevírací závorku. Vše mezi OPEN1 a CLOSE1 je uloženo v $1, vše mezi OPEN2 a CLOSE2 v $2 atd. EOL označuje prázdný řetězec na konci řádku - znak $ - a konečně END je vždy na konci.

Toto zatím nemá se srovnávaným řetězcem nic společného. Probíhá pouze překlad regulárního výrazu. Porovnávat se bude až v další fázi.

Uvádím tabulku několika častých uzlů. Kompletní je k vidění v manuálové stránce perldebguts.

UzelVýznam
Kotvy
BOLzačátek řádku
ENDkonec regulárního výrazu
EOLkonec řádku
BOUNDna hranici slova
NBOUNDmimo hranici slova
Znak z množiny znaků
ALNUMalfanumerický znak
NALNUMnealfanumerický znak
DIGITčíslice
DIGITnečíslice
SPACEbílý znak
NSPACEnebílý znak
ANYOFmnožina definovaná hranatými závorkami
ANYlibovolný znak
Kvantifikátory
STARlibovolný počet opakování
CURLYopakování definované složenými závorkami
PLUSminimálně 1 opakování
Ostatní
EXACTpřesná shoda
NOTHINGprázdný řetězec
OPENnotevírací kulatá závorka
CLOSEnuzavírací kulatá závorka

V tuto chvíli máme regulární výraz zkompilován a můžeme se pustit do porovnávání.

Matching REx `^xy\d{6}z*(1)$' against `xy123456zzz1'

Následují řádky, které postupně srovnávají zkompilovaný regulární výraz se vzorem. Syntaxe se liší podle toho, zda používáte direktivu use re "debug"; nebo use re "debugcolor";. V prvním případě je následovná:

pozice_ve_srovnávaném_řetězci <vyhovující_podřetězec> <zbývající_podřetězec> | id uzel

Konkrétně může vypadat třeba takto:

  11 <xy123456zzz> <1> | 10: OPEN1

debugcolor má tu výhodu, že spojuje <vyhovující_podřetězec> a <zbývající_podřetězec>. Vyhovující podřetězec je bíle podbarven (v článku tučně zeleně). Varianta s debugcolor je hlavně díky této vlastnosti o mnoho přehlednější.

Vezměme teď výstup řádek po řádku.

   0 <xy123456zzz1>    |  1:  BOL
   0 <xy123456zzz1>    |  2:  EXACT <xy>
   2 <xy123456zzz1>    |  4:  CURLY {6,6}
                       DIGIT can match 6 times out of 6...

1. řádek ukazuje vždy výchozí stav. Na dalším je již úspěšně nalezen znak ^ (ten je samozřejmě v každém řetězci), který ale není viditelný - proto jsme stále na pozici 0. Zajímavější je to na 3. řádku. Podbarven máme podřetězec xy. Vyhovuje totiž uzlu EXACT <xy>.

   8 <xy123456zzz1>    |  7:  STAR
                       EXACT can match 3 times out of 2147483647...

Právě jsme úspěšně nalezli 6 po sobě jdoucích číslic. Podbarveno již máme 8 znaků.

  11 <xy123456zzz1>    |  10:  OPEN1
  11 <xy123456zzz1>    |  12:  EXACT <1>
  12 <xy123456zzz1>    |  14:  CLOSE1
  12 <xy123456zzz1>    |  16:  EOL
  12 <xy123456zzz1>    |  17:  END

Dále byly nalezeny 3 znaky z a nakonec ještě znak 1. V okamžiku, kdy se regulární výraz dostane k uzlu END, skončí porovnání úspěchem.

Match successful!

Závěr

Tímto jsme definitivně skončili rozsáhlou kapitolu o regulárních výrazech. Pokud máte zájem o další informační zdroje, zde některé uvádím:

Online verze článku: http://www.linuxsoft.cz/article.php?id_article=1082