Regulární výrazy a rychlost

2.3.2006 23:17 | Přečteno: 1262× | Python | poslední úprava: 2.3.2006 23:28

Regulární výrazy jsem vždycky považoval za cosi "nečistého", co sice zjednoduší život (viz Perl), ale výkonově pomalé - prosté srovnávání řetězců by mělo být (intuitivně) rychlejší.

V oblíbeném skriptu mám hromadu (cca 150) regulárních výrazů. Jediným úkolem skriptu je uhodnout, ke kterému výrazu zadaný řetězec odpovídá a podle toho provést akci.

Protože jsem měl pocit, že v tomto místě může být úzké hrdlo aplikace, přemýšlel jsem, že bych regulární výrazy rozdělil do skupin (podle začátku) a matchoval na dvakrát - pokud bude sedět začátek, vlezu do patřičné skupiny a matchuju podruhé. Zrychlení sice konstatní, ale je rozdíl, jestli se v nejhorším případě matchuje 150 výrazů nebo nebo jenom 10.

Ejhle - matchování cca 150 výrazů (po předkompilování) trvá průměrně 0.00017s, zkompilování 0.057s (jenže to se dělá jenom jednou, takže to můžeme v klidu ignorovat).

Z toho plyne, zatím nemá smysl optimalizovat. QED.

       

Komentáře

[Kyosuke]

Tady už optimalizovali jiní...

Někteří autoři knihoven regexpů jdou tak daleko, že využívají vestavěného kompilátoru jazyka a kompilují stavový automat definovaný regulárním výrazem rovnou do nativního kódu. Výsledky jsou znát:

http://www.weitz.de/cl-ppcre/#performance

[xvasek]

Na RE je geniální právě jejich rychlost.

[Věroš]

Když se nad tím zamyslím, tak to je docela pochopitelné. Vytvoření objektu v Pythonu nejspíš není úplně levná záležitost a volání .match() nad objektem téměř celé proběhne v C.

[xvasek]

No o to C by ani tak moc nešlo, hlavní je zejména asymptotická složitost - ta je lineární časová a konstantní prostorová.

[Věroš]

Když se nad tím člověk zamyslí nad složitostí a nad tím, jak je to implementovaný, tak je to jasný

Ale na první pohled to tak nevypadá.

[xvasek]

No hlavně bacha na to, že RE jsou silně návykové...