Temat, do którego podjęcia zabierałem się już jakiś czas. Nie jest to łatwy temat, więc nie było zbyt wielu chęci ku wykonaniu testów sprawdzających wydajność niektórych popularnych sposobów pisania wyrażeń regularnych. W końcu się zabrałem i prezentuję sposoby optymalizacji wyrażeń regularnych.
Nie będę tutaj jednak opisywał podstaw wyrażeń regularnych, nie będę pisał o matematycznej ich analizie ani zagłębiał się w „wewnętrzne” procesy interpretera wyrażeń regularnych. Zajmiemy się wyłącznie wydajnością wyrażeń regularnych!
Na ten temat napisano już wiele – jakby nie patrzeć, to nawet kilka książek :-)
W swoich pomiarach starałem używać się możliwie prostych wyrażeń, tak aby skupić się jedynie na testowanych funkcjonalnościach.
Poniżej prezentuję kilka popularnych sposobów optymalizacji wyrażeń regularnych wraz z benchmarkami i krótkim objaśnieniem.
Benchmark
Do wykonywania pomiarów wykorzystam wcześniej już prezentowaną funkcję Benchmark:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | function Benchmark($function, $iterations=1000, $args=null) { set_time_limit(0); if (is_callable($function) === true) { $result = microtime(true); for ($i = 1; $i <= $iterations; $i++) { call_user_func_array($function, $args); } return round(microtime(true) - $result, 8); } return false; } |
Grupowanie
Grupowanie polega na oznaczaniu jakiegoś wybranego fragmentu wyrażenia parą nawiasów, tak aby móc przechwycić ten tekst i dalej wykorzystać (co jest bardzo często przydatne), np. :
1 2 3 4 5 | $subject = 'http://testy-zawodowe.pl'; $pattern = '/https?:\/\/.*\.([a-zA-Z]{2,5})\/?/'; preg_match($pattern, $subject, $matches); echo $matches[1]; |
W ten sposób udało się nam przechwycić domenę najwyższego poziomu, co pozwala na dalsze modyfikacje (np. dodanie flagi narodowej).
Nie o to jednak tutaj chodzi. Bardzo często trafiam na przykłady, w których jest stosowane grupowanie wyrażeń, choć później przechwycone w ten sposób fragmenty nie są wykorzystywane.
Poniżej prezentuję wyniki stosowania optymalizacji dla tego typu wyrażeń.
#1 – mała ilość danych wejściowych
Tekst trafiający do wyrażenia:
1 | http://testy-zawodowe.pl/ |
Testowane wyrażenie z niepotrzebnym grupowaniem:
1 | /(http:\/\/)(testy-zawodowe)\.(pl)/ |
Testowane wyrażenie bez grupowania:
1 | /http:\/\/testy-zawodowe\.pl/ |
Wyniki (czas wyrażony w sekundach):
| Metoda / Iteracje | 100 | 1000 | 10000 | 100000 | 1000000 |
| z grupowaniem | 0.0007 | 0.0066 | 0.0665 | 0.7464 | 6.6252 |
| bez grupowania | 0.0006 | 0.0058 | 0.0587 | 0.5724 | 5.7640 |
#2 – duża ilość danych wejściowych
Tekst trafiający do wyrażenia:
http://blog.kamilbrenk.pl/files/precle.txt
Testowane wyrażenie z niepotrzebnym grupowaniem:
1 | /(http:\/\/)(.*)\.([a-z][a-z])/ |
Testowane wyrażenie bez grupowania:
1 | /http:\/\/.*\.[a-z][a-z]/ |
Wyniki (czas wyrażony w sekundach):
| Metoda / Iteracje | 1 | 10 | 100 | 1000 | 10000 |
| z grupowaniem | 0.0039 | 0.0379 | 0.4019 | 4.119 | 41.4623 |
| bez grupowania | 0.0020 | 0.0198 | 0.2093 | 2.155 | 23.5625 |
Wyrażenie to przechodzi przez powyższą listę adresów internetowych i wybiera tylko te, które zaczynają się od http:// i kończą dwuliterową domeną (z tego co zauważyłem to domeny narodowe mają dwa znaki, być może z jakimiś wyjątkami).
Jak widać, w przypadku dużych ilości danych jest duża różnica w wydajności poszczególnych rozwiązań. Warto mieć to na uwadze :-)
Przechwytywanie
Idąc za ciosem, należy przetestować i przechwytywanie, które pozwala zapamiętać wybrane fragmenty tekstu poddane wyrażeniu.
Jak już wyżej wspomniałem, nie zawsze jest potrzebne takie zapamiętywanie – często niepotrzebnie zabiera to tylko cenne zasoby procesora.
W takim razie należy stosować składnię nie pozwalającą na przechwytywanie (mowa o operatorze ?: umieszczonym po lewym nawiasie).
#1 – mała ilość danych wejściowych
Tekst trafiający do wyrażenia:
1 | http://testy-zawodowe.pl/ |
Testowane wyrażenie z przechwytywaniem:
1 | /(http:\/\/)(testy-zawodowe)\.(pl)/ |
Testowane wyrażenie bez przechwytywania:
1 | /(?:http:\/\/)(?:testy-zawodowe)\.(?:pl)/ |
Wyniki (czas wyrażony w sekundach):
| Metoda / Iteracje | 100 | 1000 | 10000 | 100000 | 1000000 |
| z przechwytywaniem | 0.0017 | 0.0163 | 0.1427 | 0.7108 | 6.9077 |
| bez przechwytywania | 0.0015 | 0.0151 | 0.0641 | 0.6371 | 6.4058 |
#2 – duża ilość danych wejściowych
Tekst trafiający do wyrażenia:
http://blog.kamilbrenk.pl/files/precle.txt
Testowane wyrażenie z przechwytywaniem:
1 | /(http:\/\/)(testy-zawodowe)\.(pl)/ |
Testowane wyrażenie bez przechwytywania:
1 | /(?:http:\/\/)(?:testy-zawodowe)\.(?:pl)/ |
Wyniki (czas wyrażony w sekundach):
| Metoda / Iteracje | 1 | 10 | 100 | 1000 | 10000 |
| z przechwytywaniem | 0.0049 | 0.0543 | 0.5524 | 5.7088 | 67.2913 |
| bez przechwytywania | 0.0028 | 0.0300 | 0.3152 | 3.2365 | 33.4211 |
I tutaj wyraźnie widać, że przy większych ilościach danych różnice są bardzo wyraźne.
Kwantyfikatory zachłanne
Bardzo często trafiam na nadmierne wykorzystywanie kwantyfikatorów zachłannych w miejscach, gdzie wystarczyłoby zwykłe określenie pożądanych wartości ciągu trafiającego pod wyrażenie.
Mówiąc jaśniej, chcemy przeanalizować wprowadzony kod pocztowy. Kod pocztowy ma następujący format: XX-XXX, gdzie X to liczba od 0 do 9. Przykład wyrażenia z niepotrzebnym wykorzystaniem zachłanności:
1 | /[[:digit:]]+-[[:digit:]]+/ |
Dlaczego to wyrażenie jest złe? Ano bardziej wydajnie można napisać to bez użycia zachłanności:
1 | /[[:digit:]][[:digit:]]-[[:digit:]][[:digit:]][[:digit:]]+/ |
Poniżej prezentuję benchmark dla wyrażeń zawierających operatory zachłanne i wyrażeń niewykorzystujących zachłanności.
#1 – mała ilość danych wejściowych
Tekst trafiający do wyrażenia:
1 | http://testy-zawodowe.pl |
Testowane wyrażenie z operatorami zachłannymi:
1 | /.*:\/\/www\.testy-zawodowe\..*/ |
Testowane wyrażenie bez operatorów zachłannych:
1 | /http:\/\/www\.testy-zawodowe\.pl/ |
Wyniki (czas wyrażony w sekundach):
| Metoda / iteracje | 100 | 1000 | 10000 | 100000 | 1000000 |
| zachłanne | 0.0027 | 0.0269 | 0.1788 | 1.1507 | 11.4565 |
| niezachłanne | 0.0013 | 0.0138 | 0.0572 | 0.5677 | 5.7788 |
#2 – duża ilość danych wejściowych
Tekst trafiający do wyrażenia:
http://blog.kamilbrenk.pl/files/precle.txt
Testowane wyrażenie z operatorami zachłannymi:
1 | /.*:\/\// |
Testowane wyrażenie bez operatorów zachłannych:
1 | /http:\/\// |
Wyniki (czas wyrażony w sekundach):
| Metoda / iteracje | 1 | 10 | 100 | 1000 | 10000 |
| zachłanne | 0.0142 | 0.1468 | 1.4856 | 14.4443 | 143.4883 |
| niezachłanne | 0.0012 | 0.0094 | 0.1214 | 1.0811 | 10.9888 |
W przypadku obu wyrażeń pobieramy wszystkie adresy zaczynające się od HTTP. W powyższej liście adresów wszystkie adresy zaczynają się w ten sposób, myślę więc, że próba jest całkiem dobrze przedstawiona (zwracany jest ten sam wynik).
Jak widać, kwantyfikatory zachłanne spowalniają wykonywanie wyrażeń, czasem nawet wielokrotnie dłużej (w zależności od złożoności wzorca).
Przykładowo, bardzo często widzę stosowanie niniejszego wzorca:
1 | ^(.*)$ |
Co w tym złego? Ano wzorzec ten wymusza na mechanizmie wyrażenia regularnego przeanalizowanie całego ciągu tekstowego i porównanie każdego znaku z symbolem wieloznaczności (. – kropka) w celu sprawdzenia, czy znak pasuje do wzorca. Oczywiście każdy znak pasuje do tego wzorca – jednak ciąg o n znakach będzie powodował wykonanie n operacji porównania.
Kilka wystąpień tego samego ciągu
Kolejny przykład dotyczy optymalizacji wyrażeń, w których musimy analizować ciągi zawierające kilka tych samych znaków.
Przykładem takiego ciągu jest numer telefonu, np. „tel. 609234934″. Jak najwydajniej przeanalizować taki ciąg? Do wyboru mamy kilka możliwości.
#1 – mała ilość danych wejściowych
Tekst trafiający do wyrażenia:
1 | 693988422 |
Z wykorzystaniem kwantyfikatorów zachłannych (zachłanne-1):
1 | /[0-9]+/ |
Z wykorzystaniem kwantyfikatorów zachłannych, określając liczbę wystąpień ciągu (zachłanne-2):
1 | /[0-9]{9}/ |
Oraz przypadek bez wykorzystania zachłanności (niezachłanne):
1 | /[0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9]/ |
Wyniki (czas wyrażony w sekundach):
| Metoda / iteracje | 100 | 1000 | 10000 | 100000 | 1000000 |
| zachłanne-1 | 0.0007 | 0.0069 | 0.0687 | 0.6930 | 6.8986 |
| zachłanne-2 | 0.0006 | 0.0060 | 0.0606 | 0.5956 | 5.9913 |
| niezachłanne | 0.0007 | 0.0064 | 0.0647 | 0.6588 | 6.3716 |
#2 – duża ilość danych wejściowych
Tekst trafiający do wyrażenia:
http://blog.kamilbrenk.pl/files/numerki.txt (2.000 losowych 9-cyfrowych numerów)
Z wykorzystaniem kwantyfikatorów zachłannych (zachłanne-1):
1 | /[0-9]+\n/ |
Z wykorzystaniem kwantyfikatorów zachłannych, określając liczbę wystąpień ciągu (zachłanne-2):
1 | /[0-9]{9}\n/ |
Oraz przypadek bez wykorzystania zachłanności (niezachłanne):
1 | /[0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9]\n/ |
Wyniki (czas wyrażony w sekundach):
| Metoda / iteracje | 1 | 10 | 100 | 1000 | 10000 |
| zachłanne-1 | 0.0061 | 0.0622 | 0.6017 | 6.0703 | 60.9530 |
| zachłanne-2 | 0.0051 | 0.0492 | 0.4906 | 4.8685 | 48.7464 |
| niezachłanne | 0.0057 | 0.0545 | 0.5907 | 5.3848 | 53.8382 |
Jak widać po wynikach testu, najbardziej wydajnym rozwiązaniem jest zastosowanie kwantyfikatora zachłannego określającego ilość wystąpień powtórzeń.
Najgorszym natomiast rozwiązaniem jest zastosowanie zachłanności „nieograniczonej” (mowa tutaj o operatorze * oraz +).
W niektórych przypadkach najlepszym jednak rozwiązaniem jest samodzielne wypisanie ilości powtórzeń danego ciągu (by nie zaciągać do tego operatorów zachłannych, które czasami potrafią nieźle obciążyć maszynę, na której są wykonywane).
Modyfikatory
Kolejny test dotyczyć będzie wykorzystania modyfikatora i, który sprawia iż wielkość liter jest ignorowana w ciągu trafiającym do wyrażenia.
Lepiej jest stosować ten modyfikator czy samodzielnie wypisywać wielkie litery w przedziałach, gdzie będzie to konieczne? Przekonajmy się!
#1 – mała ilość danych wejściowych
Tekst trafiający do wyrażenia:
1 | PacMan |
Testowane wyrażenie z modyfikatorem:
1 | /[a-z]{6}/i |
Testowane wyrażenie bez modyfikatora:
1 | /[a-zA-Z]{6}/ |
Wyniki (czas wyrażony w sekundach):
| Metoda / iteracje | 100 | 1000 | 10000 | 100000 | 1000000 |
| z modyfikatorem | 0.0013 | 0.0131 | 0.1268 | 1.2850 | 12.884 |
| bez modyfikatora | 0.0015 | 0.0131 | 0.1311 | 1.3541 | 13.2853 |
#2 – duża ilość danych wejściowych
Tekst trafiający do wyrażenia:
Hypertext Transfer Protocol — HTTP/1.0
Testowane wyrażenie z modyfikatorem:
1 | /http/i |
Testowane wyrażenie bez modyfikatora:
1 | /[Hh][Tt][Tt][Pp]/ |
Wyniki (czas wyrażony w sekundach):
| Metoda / iteracje | 1 | 10 | 100 | 1000 | 10000 |
| z modyfikatorem | 0.0046 | 0.0177 | 0.1717 | 1.7297 | 18.1458 |
| bez modyfikatora | 0.0869 | 0.3960 | 3.6655 | 36.6532 | 371.6014 |
Jak widać, jest tutaj niemała różnica w wydajności poszczególnych rozwiązań. I co najdziwniejsze, wyrażenie z modyfikatorem wykonuje się kilkanaście razy szybciej niż bez modyfikatora!
Jest to o tyle dziwne, że czytając kiedyś książkę o wyrażeniach regularnych autor sugerował, by jak najmniej używać modyfikatora /i. Niestety powyższy test nie potwierdza tych teorii (a wykonałem kilkanaście różnych testów, gdyż byłem przekonany, że to ja robię źle testy). Czy może faktycznie robię coś źle?
Podsumowanie
Jak można zobaczyć na powyższych benchmarkach, są to w większości przypadków mikro-optymalizacje mające niewielki wpływ na działanie aplikacji.
Niemniej jednak czasami musimy przeprowadzić wiele testów i walidacji z użyciem wyrażeń regularnych po stronie serwera dla każdego użytkownika, co już znacząco może wpłynąć na wykorzystanie procesora. Innym razem musimy wykonywać testy po stronie klienta po każdej zmianie wartości w aktywnym polu. Dobrze więc, aby tworzone przez nas wyrażenia były optymalne i działały bez zarzutów!
Aby spełnić te wymagania, pamiętaj by zawsze testować różne rozwiązania oraz pisać możliwie optymalne rozwiązania (choć czasem przejrzystość i prostota rozwiązania jest ważniejsza niż wydajność).
Pozostaje mi życzyć powodzenia przy pisaniu własnych wyrażeniach regularnych! Dziękuję także za ewentualne uwagi i porady od osób mających większe doświadczenie w temacie optymalizacji wyrażeń.
Jak byś mógł zrobić ten sam test ale na dłuższym tekście. Ciekawi mnie różnica wydajności miedzy kilkoma słowami a artykułem.
Zrobiłem testy dla większych ilości danych wejściowych, teraz lepiej widać efekty poszczególnych rozwiązań :-)
Cóż trochę nieprzemyślane te testy, żeby nie powiedzieć absurdalne, porównywać można dwie rzeczy które oferują taką samą funkcjonalność, cztery pierwsze testy są do niczego nie przydatne. Natomiast piąty porównuje dwa sposoby realizacji tego samego i pokazuje który jest lepszy, całe szczęście doczytałem do końca.
@eN: wszystkie testy zwracają te same dane, tylko realizują to w odmienny sposób (tak jak pisałem, często trafiam na wyrażenia z niepotrzebnymi nawiasami grupującymi czy niepotrzebną zachłannością), stąd takie porównania :-)
A może mógłbyś zasugerować testy, które lepiej i realniej obrazowałyby wydajność poszczególnych rozwiązań?
hehe, a teraz dodaj kolejne testy dla ereg :D co prawda znika w 5.3 – ale :D
Toto można zapisać w jeszcze dziwniejszy sposób
a chyba najlepiej zapisał byś tak
Tak czy siak – wyrażenia regularne to spory kawał teorii i praktyki do przerobienia by ogarnąć to na przyzwoitym poziomie.
Co do stosowania modyfikatorów (u mnie to się zwało przełącznikami (?) ) – wszystko zależy od implementacji, ereg i preg (już pomijam fakt że składnia preg jest zgodna z RegExp’ami JS)
ereg pominąłem całkowicie, bo to przeżytek – jest wolniejsze, mniej bezpieczne i ogólnie nikomu niepotrzebne (manual: This function has been DEPRECATED as of PHP 5.3.0. Relying on this feature is highly discouraged. :D).
Zrobiłem też test dla:
jednak stosując dodatkowo alternatywę (znaczek |) wyrażenia wykonywały się już znacząco wolniej (parę razy wolniej w stosunku do wyrażenia:
dlatego od razu odpuściłem :-)
Robiłem też kilka innych testów, ale myślę że te powyższe były najciekawsze i różnice były najbardziej widoczne :-)
Wyrażenia regularne to ciężki kawałek chleba i niewątpliwie kiedyś jeszcze wrócę do nadgryzienia kolejnego kawałka :D
Jak na studiach będziesz mieć AS i DAS to wiele się wyjaśni – u mnie na polibudzie był od tego świetny prowadzący i to całe RegExpy stały się jasne :)
DAS / AS? Pierwsze słyszę :-) Raczej nie będę już miał takich wynalazków na studiach, niewiele tam się nauczyłem, co mogłoby mi się przydać w pracy programisty, niestety.
Z tego co widziałem w planie to zostały mi chyba tylko bazy danych (Microsoft Access i podstawy SQL) :P
DAS – deterministyczne automaty skończone, AS – to samo ale bez D :)
Problem w tym że nie zwracają tego samego, a dokładniej
1 Grupowanie:
a) z grupowaniem – mamy dostęp do podciągów
b) bez grupowania – nie mamy dostępu do podciągów
Cóż oczywistą sprawą jest że jeśli używasz czegoś co Ci nie jest potrzebne to będzie działało siłą rzeczy dłużej, więc po co to testować.
2) Przechwytywanie
Patrz pkt 1.
Ciekawym porównaniem byłby wyrażenia w których musimy skorzystać z grupowania czyli przy używaniu operatora | a nie potrzebujemy przechwytywania: (czarny|czerwony)balonik vs (?:czarny|czerwony)balonik. Zwykle stosuje się to pierwsze bo ładniej wygląda, pytanie czy dużo przez to tracimy wydajności ;).
3 Kwantyfikatory zachłanne
a) zachłanne – „/.*:\/\/www\.testy-zawodowe\..*/”
b) niezachłanne – „/http:\/\/www\.testy-zawodowe\.pl/”
Kontrprzykład: „mam://.www.testy-zawodowe.cosnietak” pasuje do wzorca A nie pasuje do wzorca B, więc te wzorce są różne i ich porównanie mija się z celem.
4) Kilka wystąpień tego samego ciągu
a) zachłanne-1 – „/[0-9]+/”
b) zachłanne-2 – „/[0-9]{9}/”
c) niezachłanne – „/[0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9]/”
Kontrprzykład: „123456787563″ pasuje do A, a nie pasuje do B , C (B i C są takie same). Więc porównanie B i C ma sens.
A pojęcie (nie)zachłanności odnosi się do kwantyfikatorów i było nadużywane w powyższych dwóch testach, które raczej powinny się nazywać wyrażenie z kwantyfikatorem(3a,4a,4b) vs bez kwantyfikatora (3b,4c). Swoją drogą 4b zachłanne wcale nie jest.
5) Jedyny test który jest wartościowy bo testuje dwie metody realizacji tego samego.
I swoją drogą ciężko w wyrażeniach regularnych o dwa różne wzorce realizujące to samo na prostych przykładach, zwykle istnieje tylko jeden poprawny wzorzec.
@eN: Nie sposób się nie zgodzić z tym co piszesz, masz rację. Wezmę pod uwagę powyższe uwagi i przy kolejnych testach postaram się lepiej dobierać wyrażenia do testów – a na pewno jeszcze będę wracał do wyrażeń regularnych.
Dziękuję więc za przydatne rady, lubię takie komentarze :-)