Wczoraj napisałem, że przy walidacji nie należy stosować "rozwlekłych" wyrażeń regularnych, z uwagi na ewentualne problemy z wydajnością. Dzisiaj na szybko sprawdziłem jak ta teza ma się do rzeczywistości.
O walidacji \d+
Napisałem dwa skrypty (w Pythonie oczywiście), jeden, który generuje 500 000 losowych linii, w których skład wchodzą znaki:
- litery (string.letters),
- cyfry (string.digits),
- inne znaki (string.punctuation),
Długość każdej linii była losowa i wynosiła od 1 do 100 znaków. Tak przygotowany materiał testowy był sprawdzany przez drugi skrypt. Skrypt ten miał za zadanie sprawdzić wydajność czterech wyrażeń regularnych:
- ^(\d+)$,
- ^(\d+).*$,
- ^.*(\d+).*$,
- .*(\d+).*,
Zakładałem, że wydajność będzie zgodna z powyższą kolejnością. Test polegał na sprawdzeniu każdym z wyrażeń regularnych testowego pliku. Test wykonany był 10 razy, za wynik brana była wartość średnia. Oto wyniki:
- Pattern: ^(\d+)$, wynik: 2.034400
- Pattern: ^(\d+).*$, wynik: 2.062500
- Pattern: .*(\d+).*, wynik: 2.843700
- Pattern: ^.*(\d+).*$, wynik: 2.901500
Cóż, co do pierwszych dwóch miejsc nie pomyliłem się, choć różnica w czasie nie jest zbyt duża. Miejsce 3 i 4 były odmienne od moich oczekiwań, choć różnica rzędu 0,06 sekundy nie jest zbyt znacząca. Różnica między miejscem 1 i 2 jest jeszcze mniejsza - niecałe 0,03 sekundy. Różnica między najwolniejszym i najbardziej wydajnym przypadkiem to 0,87 sekundy (najgorszy jest o około 40% gorszy niż przypadek najlepszy).
Co to dowodzi? W zasadzie nic. Pokazuje, że walidator sprawdzający (lub wyszukujący określonych danych) wykorzystujący wyrażenie regularne może być bardziej lub mniej wydajny. Z drugiej strony różnica ta nie jest bardzo istotna. Nie oznacza to jednak, że taka nie może być. Dla każdego algorytmu jego złożoność (a co za tym idzie - czas wykonania) można rozpatrywać z punktu widzenia przypadku najlepszego, przypadku "normalnego" oraz przypadku najgorszego. Być może analizując sposób implementacji wyrażeń regularnych w konkretnym języku, udało by się znaleźć taki przypadek, dla którego różnice między poszczególnymi wersjami wyrażenia będzie bardziej istotna.
Nie, nie wymyśliłem tego sam, w 2003 roku pojawił się dokument Denial of Service via Algorithmic Complexity Attacks. Swoją drogą wydaje mi się, że znikomy odsetek programistów przy tworzeniu aplikacji zastanawia się obecnie nad złożonością obliczeniową stosowanych algorytmów. Przecież to można "skalować", dołożyć ze dwa serwery i będzie super. No i nie zapominajmy o 16 procesorowym serwerze pod bazę danych...
