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:

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:

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ů.

Nastavíme počet opakování:

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

A můžeme volat cmpthese:

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

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:

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

Program jako obyčejně spustíme:

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.

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

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á:

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

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.

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>.

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

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.

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:

• perlre(1) - popis syntaxe regulárních výrazů v Perlu
• perlrequick(1) - vysvětluje základy regulárních výrazů
• perlretut(1) - tutoriál na téma Perl a regulární výrazy
• perlop(1), oddíly Regexp Quote-Like Operators a Gory details of parsing quoted constructs - operátory v Perlu pro práci s regulárními výrazy
• perlfaq6(1) - časté otázky
• perldebguts(1), oddíl Debugging regular expressions - sledování průběhu vyhodnocování regulárních výrazů
• kniha Mastering Regular Expressions, Jeffrey Friedl, O'Reilly and Associates. Česká recenze vyšla na serveru linuxzone.cz
• existují weby zaměřené přímo na regulární výrazy - namátkou www.regular-expressions.info nebo www.regularnivyrazy.info.
• řada článků a tutoriálů na Internetu, z nichž nemohu opomenout vynikající dílo Pavla Satrapy na www.kit.vslib.cz/~satrapa/docs/regvyr/all.html nebo práci Pavla Dařeny.
• www.regexlib.com - zde je archiv regulárních výrazů. Dříve, než začnete psát složitější regulární výraz, se podívejte sem. Možná už někdo měl stejný problém.