Słaba wydajność wyrażeń regularnych?

Wysłane przez Eyala Schneidera, 21 maja 2009 r. Pakiet java.util.regex został dodany do języka Java w wersji 1.4. Jest to bardzo potężne narzędzie i trzeba zostać mistrzem, aby poprawnie z niego korzystać. Nawet jeśli wyrażenie regularne jest prawdziwe, może działać bardzo wolno, jeśli nie zostanie napisane inteligentnie. Kontynuuj czytanie, jeśli chcesz zrozumieć przyczynę problemów, lub przewiń do końca strony, gdzie znajdziesz 10 przydatnych wskazówek dotyczących poprawy wydajności wyrażeń regularnych w Javie.

Czy to naprawdę jest takie powolne?

Załóżmy, że chcemy wybrać tylko linie zawierające ciąg znaków „a” i „b”. Prawidłowym rozwiązaniem może być: (a*b*)* Jeśli jednak uruchomisz wyrażenie z na przykład ciągiem „aaaaaaaaaaaaaaaaaaaaaaaaaaaax”, upłynie kilka minut, zanim zakończy się i nie zgłosi żadnych dopasowań! Oczywiście najlepszym wyrażeniem regularnym w tym przypadku byłoby: (a|b)* Na moim komputerze z tym samym ciągiem znaków zajmuje to mniej niż milisekundę. Ewidentnie jest tu problem z wydajnością.

Dlaczego to się dzieje?

Podobnie jak większość silników wyrażeń regularnych, Java wykorzystuje podejście NFA (niedeterministyczne automaty skończone). Silnik skanuje komponenty wyrażenia regularnego jeden po drugim i odpowiednio przechodzi przez ciąg wejściowy. Może także wrócić do początku, aby znaleźć odpowiednie alternatywy, jeśli dotrze do „ślepego zaułka”. Alternatywne wyniki uzyskuje się stosując struktury regularne, takie jak kwantyfikatory ( *, +, ? ) i alternacje (np. a|b|c|d ). Ta technika badawcza nazywa się backtrackingiem. W okropnym przykładzie powyżej silnik będzie przeglądał WSZYSTKIE serie rozkładów symbolu „a” na mniejsze serie, aż zorientuje się, że nie ma żadnych dopasowań. Ten przykład pokazuje, jak algorytm śledzenia wycofywania może skutkować wykładniczym oszacowaniem czasu (w zależności od długości ciągu wejściowego). Pokazuje to również ważną właściwość NFA: zawsze będą najgorsze przypadki, które prawie pasują do wzorca. Jeśli zostanie znalezione dopasowanie, wyszukiwanie zostanie zatrzymane. Innym głównym podejściem do użycia w wyrażeniach regularnych jest DFA (Deterministyczny automat skończony). W tym podejściu wyrażenie regularne w rzeczywistości buduje automat używany do przechodzenia przez ciągi wejściowe znak po znaku bez cofania się. Daje to czas liniowy całemu wejściu, niezależnie od złożoności wyrażenia regularnego. Zamiast sekwencyjnie skanować ciąg znaków w poszukiwaniu dopasowań (jak w NFA), DFA symuluje skanowanie równoległe. Dlaczego więc Java (oraz .NET, Perl, Python, Ruby, PHP itp.) używają NKA, a nie DKA, które zachowuje się znacznie lepiej? Powodem jest to, że NKA ma wiele znaczących zalet:

Kompiluje się szybciej i wymaga znacznie mniej pamięci
Umożliwia kilka przydatnych funkcji (szczegóły można znaleźć w samouczku firmy Sun ):

Przechwytywanie grupowe i linki zwrotne
Kontrola pozycji
Rozszerzone kwantyfikatory (chciwe i leniwe)

Należy zauważyć, że popularne terminy NKA i DKA są nieprecyzyjne, gdy są używane w kontekście wyrażeń regularnych. Teoretycznie te dwa modele mają taką samą moc obliczeniową. Oznacza to, że nie można zapisać w jednym modelu automatu wyrażenia regularnego, którego nie dałoby się wyrazić w innym. W praktyce istnieje zapotrzebowanie na więcej możliwości, aby oba typy implementacji różniły się semantyką. Silniki NKA zapewniają większą elastyczność, co czyni je lepszymi od DKA pod względem mocy obliczeniowej. Ze względu na szybkość DFA i unikalne cechy NFA istnieją jeszcze 2 „prefabrykowane” sposoby implementacji wyrażeń regularnych. Niektóre implementacje korzystają z obu typów (np. GNU egrep, który wybiera konkretny silnik w czasie wykonywania), a niektórym udało się zaimplementować wersję prawdziwie hybrydową (np. wyrażenia regularne Tcl) ze wszystkimi korzyściami.

Porada

Poniżej znajduje się kilka wskazówek, jak uniknąć problemów z wydajnością wyrażeń regularnych w Javie. Wiele z nich ma na celu zmniejszenie zysków.

1) Wstępna kompilacja

Banalne, ale warte wspomnienia. Jeśli użyjesz wyrażenia regularnego więcej niż raz, pamiętaj o skompilowaniu go wcześniej:

// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);

2) Kwantyfikatory leniwe a kwantyfikatory zachłanne

Domyślnie kwantyfikatory ( * + ? ) są zachłanne. Oznacza to, że rozpoczynają dopasowywanie od najdłuższej możliwej sekwencji, a następnie, jeśli to konieczne, stopniowo wracają do poprzedniego stanu. Jeśli z góry wiesz, że dopasowania będą zazwyczaj krótkie, powinieneś użyć leniwych kwantyfikatorów. Zaczynają od najmniejszego dopasowania i w razie potrzeby idą dalej. Powiedzmy, że chcemy znaleźć tylko linie pasujące do sekwencji „cześć”. Zwykłe .*hello.* zrobi wszystko dobrze, ale jeśli wiemy, że „hello” zwykle pojawia się bliżej początku tekstu, to .*?hello.* będzie działać średnio szybciej.

3) Jeśli to możliwe, używaj kwantyfikatorów super zachłannych

W przeciwieństwie do leniwych kwantyfikatorów, które wpływają na wydajność, ale nie wpływają na regularne zachowanie, super-chciwe kwantyfikatory mogą w rzeczywistości zmienić znaczenie wyrażenia regularnego. Kiedy **+ zostanie użyte zamiast * , pierwsze dopasowanie będzie zachłanne (to znaczy największe możliwe, jakby było po prostu *), ale w przypadku niepowodzenia nie będzie możliwości powrotu, nawet jeśli spowoduje to niepowodzenie całego wyszukiwania. Kiedy może się to przydać? Załóżmy, że musimy znaleźć tekst w cudzysłowie. Zwykłe „[^”]*” będzie działać dobrze. Jednak w przypadkach przeczących spowoduje niepotrzebne wcięcia (na przykład „bla bla bla). Użycie „[^”]*+” wyeliminuje wycofanie zmian bez zmiany znaczenia wyrażenia. Niezależne grupowanie pozwala osiągnąć ten sam efekt i daje jeszcze większą kontrolę (zobacz poradnik Suna ).

4) Unikaj przechwytywania grupowego

Każde wyrażenie w nawiasach jest domyślnie uznawane za grupę. Ma to niewielki wpływ na wydajność. Jeśli to możliwe, spraw, aby Twoje grupy były „nie do przechwycenia”, zaczynając od (?: zamiast ( .

5) Używaj mądrze przeplatania

Gdy używane jest przeplatanie (np. Paul|Jane|Chris ), kolejność, w jakiej silnik próbuje dopasować opcje, jest taka sama, jak kolejność, w jakiej się one pojawiają. Możesz skorzystać z tej funkcji i umieścić najpopularniejsze opcje bliżej początku. Poprawi to średni czas pozytywnej odpowiedzi.

6) Unikaj dwuznaczności

Zapisuj wyrażenia regularne w taki sposób, aby zminimalizować liczbę różnych dopasowań w ciągu wejściowym. Na przykład: wyrażenie regularne (a*b*)* podane na początku artykułu umożliwia interpretację ciągu „aabb” na zbyt wiele sposobów: (a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp (a|b)* natomiast interpretuje jedynie unikalność kombinacje pozytywnie. Jest to bardzo ważne, aby zmniejszyć zyski w przypadkach bliskich dopasowania.

7) Podgląd

Podgląd umożliwia dodanie ograniczeń sekwencji po lewej/prawej stronie bieżącej pozycji. W szczególności, stosując negatywne spojrzenie w przód, można wyszukiwać linie, które nie zawierają jakiegoś ciągu (co byśmy bez tego zrobili!). W jaki sposób może to pomóc zwiększyć produktywność? Załóżmy, że chcemy pobrać adres URL z tagu linku. Rozważ następujące wyrażenie regularne: a .* href=(\S*).*/ w przypadku zwykłych tagów to wyrażenie będzie pasować do adresu tylko wtedy, gdy tekst zawiera atrybut „href” (\S jest używany do wszystkich znaków z wyjątkiem ograniczników). Ale na przykład w przypadku niektórych nietypowych tagów nastąpi wycofanie. Na przykład: „a href= href=href=…. href=coś.” Poniższe wyrażenie regularne zapobiegnie takiej sytuacji podczas zastępowania „.*” w wyrażeniu czymś, co nie pasuje do „href”: a ((?!href).)* href=(\S*)((?!href).)*/

8) Określ długość

Java zawiera optymalizator wyrażeń regularnych, który sprawdza długość łańcucha wejściowego względem minimalnej i maksymalnej długości uzyskanej z wyrażenia regularnego. Dzięki temu w niektórych przypadkach możesz natychmiast przerwać wyszukiwanie. Aby wspomóc ten mechanizm, w miarę możliwości należy określić liczbę powtórzeń (na przykład [01]{6} dopasowuje wszystkie ciągi binarne o długości sześciu znaków).

9) Wybierz identyczne linie

Czasami takie same ciągi znaków są ukryte w grupach lub alternatywach: (hello|hell|heel) To wyrażenie można uprościć do: he(llo|ll|el) W ten sposób dajemy optymalizatorowi wyrażenia regularnego więcej informacji.

10) Przetestuj wyrażenie regularne

Rozsądnym może być najpierw przetestowanie wyrażenia regularnego, jeśli będzie ono używane w aplikacji, w której wydajność ma kluczowe znaczenie. Napisz mikrotest porównawczy, który przetestuje Twoje wyrażenie na różnych danych wejściowych. Pamiętaj, aby przeprowadzać testy na danych o różnej długości, a także na danych ściśle odpowiadających Twojej próbce.

Spinki do mankietów:

http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -of-Przetwarzanie-Wyrażenia/