Jak faktycznie działają wyrażenia regularne?

30

Powiedz, że masz dokument z napisanym esejem. Chcesz przeanalizować ten esej, aby wybrać tylko niektóre słowa. Fajne.

Czy użycie wyrażenia regularnego jest szybsze niż parsowanie pliku wiersz po wierszu i słowo po słowie w poszukiwaniu dopasowania? Jeśli tak, jak to działa? Jak możesz iść szybciej niż patrzeć na każde słowo?

lazeR
źródło
5
Zakładasz (co oznacza zero dowodów), że wyrażenie regularne będzie szybsze, ale nie wiesz, dlaczego tak jest? Może wtedy powinieneś ponownie rozważyć swoje założenie.
pdr
3
stąd założenie. gdybym miał dowód, nie byłby to jeden, prawda?
lazeR
4
Nie o to chodzi. Chodzi o to, co doprowadziło cię do tego założenia ... Nie potrzebujesz dowodów na swoje pytania, ale potrzebujesz uzasadnienia swoich założeń.
yannis
1
err, nie każdy znak ciągu wejściowego po prostu przenosi maszynę stanu do następnego stanu. Nie wiem, jak ktokolwiek mógłby spowolnić tę operację ...
tp1,
2
Nie jestem pewien, czy jest szybszy, ale mój główny powód używania wyrażeń regularnych wynika z elegancji złożonych dopasowanych wzorców, po prostu nie znajdziesz lepszego sposobu na wyrażenie tego w środowisku kodowania.
Mantorok

Odpowiedzi:

47

Jak to działa?

Spójrz na teorię automatów

Krótko mówiąc, każde wyrażenie regularne ma równoważny automat skończony i może zostać skompilowane i zoptymalizowane do automatu skończonego. Zaangażowane algorytmy można znaleźć w wielu książkach kompilatorów. Algorytmy te są używane przez programy uniksowe, takie jak awk i grep.

Jednak większość współczesnych języków programowania (Perl, Python, Ruby, Java (i JVM), C #) nie korzysta z tego podejścia. Używają rekurencyjnego podejścia do cofania, które kompiluje wyrażenie regularne w drzewo lub sekwencję konstrukcji reprezentujących różne podgrupy wyrażenia regularnego. Większość współczesnych składni „wyrażeń regularnych” oferuje odsyłacze wsteczne spoza grupy języków regularnych (nie mają reprezentacji w automatach skończonych), które można w trywialny sposób zastosować w rekurencyjnym podejściu wstecznym.

Optymalizacja zwykle daje bardziej wydajną maszynę stanu. Na przykład: rozważ aaaab | aaaac | aaaad, zwykły programista może uzyskać prostą, ale mniej wydajną implementację wyszukiwania (porównując trzy łańcuchy osobno) w ciągu dziesięciu minut; ale zdając sobie sprawę, że jest to równoważne z aaaa [bcd], lepsze wyszukiwanie można przeprowadzić, wyszukując pierwsze cztery „a”, a następnie testując 5. znak na [b, c, d]. Proces optymalizacji był jednym z moich domowych zadań kompilatora wiele lat temu, więc zakładam, że ma to miejsce także w większości nowoczesnych silników wyrażeń regularnych.

Z drugiej strony maszyny stanowe mają pewną przewagę, gdy akceptują ciągi, ponieważ zajmują więcej miejsca w porównaniu z „trywialną implementacją”. Zastanów się nad programem, który usuwa znaki cytowania z ciągów SQL, to znaczy: 1) zaczyna się i kończy pojedynczymi znakami cudzysłowu; 2) pojedyncze cudzysłowy są poprzedzane dwoma kolejnymi pojedynczymi cudzysłowami. Tak więc: input ['a' ']] powinno dać wynik [a']. W maszynie stanów kolejne znaki pojedynczego cudzysłowu są obsługiwane przez dwa stany. Te dwa stany służą do zapamiętania historii wprowadzania, dzięki czemu każdy znak wejściowy jest przetwarzany dokładnie tylko raz, jak pokazano poniżej:

...
S1->'->S2
S1->*->S1, output *, * can be any other character 
S2->'->S1, output '
S2->*->END, end the current string

Tak więc, moim zdaniem, wyrażenie regularne może być wolniejsze w niektórych trywialnych przypadkach, ale zwykle szybsze niż ręcznie spreparowany algorytm wyszukiwania, biorąc pod uwagę fakt, że optymalizacja nie może być niezawodnie wykonana przez człowieka.

(Nawet w trywialnych przypadkach, takich jak wyszukiwanie ciągu, inteligentny silnik może rozpoznać pojedynczą ścieżkę na mapie stanów i zredukować tę część do prostego porównania ciągu i uniknąć zarządzania stanami.)

Określony silnik z frameworka / biblioteki może być powolny, ponieważ silnik wykonuje wiele innych rzeczy, których programista zwykle nie potrzebuje. Przykład: klasa Regex w .NET tworzy zestaw obiektów, w tym Dopasuj, Grupy i Przechwyty.

Codism
źródło
2
Nie mógłbym tego lepiej powiedzieć. Jedyne, co chciałbym dodać: wyrażenia regularne mogą nadrobić zaległości w programowaniu. W przykładzie wspomniałeś aaaab|aaaac|aaaadVs. aaaa[bcd]. Warto wyraźnie stwierdzić, że oba są matematycznie równoważne i wytwarzają ten sam DFA, dając tym samym programistom więcej swobody w reprezentowaniu wyrażeń regularnych w sensowny sposób (nie to, że jest to powszechna praktyka, ale ... wiesz). ..
riwalk 30.11.11
Dzięki, to faktycznie miało sens dzięki klasie automatów, którą wziąłem
lazeR
Czy to przykład trywialnego problemu, w którym wyrażenie regularne jest nadmierne ?: stackoverflow.com/questions/18955099/…
Menelaos Bakopoulos
17

Wyrażenia regularne wyglądają szybko, ponieważ masz szybkie komputery.

W latach osiemdziesiątych, gdy 1 MIPS był szybkim komputerem, wyrażenia regularne były dość dużym obszarem zmartwień, obaw i badań, ponieważ były powolne, brzydkie i wymagały dużej mocy obliczeniowej. Nastąpił sprytny rozwój algorytmu i pomógł - ale dla wszystkich praktycznych celów obecnie widzisz cud szybkich maszyn przesuwających się po pęknięciach.

szybko
źródło
2
Jeśli szukasz tylko jednego słowa, obie metody są takie same (lub wyrażenie regularne jest nieco wolniejsze). Ale biorąc pod uwagę złożone wyrażenie (i tekst o dość dużym rozmiarze), wyrażenie regularne będzie prawdopodobnie szybsze niż proste wyszukiwanie (zakładając, że piszesz proste wyszukiwanie (zawsze możesz napisać złożone wyszukiwanie, które jest tak szybkie)). Teraz, gdy pogoda jest znacząca, jest to zbyt ogólne pytanie i będziesz musiał spojrzeć na to indywidualnie.
Martin York
3
-1. Teoria wyrażeń regularnych sięga lat 50. i była pomocna w tworzeniu analizatorów leksykalnych (a przez to kompilatorów). Tworzą bardzo wydajne maszyny stanów, które (możliwe) wykorzystują jak najmniejszą liczbę stanów. Wynikowe maszyny stanów mogą dopasowywać złożone wzory znacznie szybciej niż cokolwiek, co można napisać ręcznie. Wyglądają szybko, ponieważ są szybkie.
riwalk
Mogłem trochę nie zauważyć mojego punktu. Mogą być „szybkie”, ale to wszystko względne - wciąż jest wiele do zrobienia. Niektóre z pozostałych odpowiedzi tutaj również są czytelne.
szybko_now
Czy ta odpowiedź dotyczy pytania? i jak 13 entuzjastów?
Sadanand
7

Jak myślisz, dlaczego są szybsi niż przeszukiwanie dokumentu?

Istnieje kilka sztuczek, które możesz zrobić, np. jeśli szukasz 10-literowego słowa zaczynającego się od A i kończącego się na B, to jeśli znajdziesz A, a znak 9 pozycji dalej nie jest B, możesz go pominąć. patrz algorytm Knuth – Morris – Pratt

Martin Beckett
źródło
5

Co sprawia, że ​​wyrażenie regularne jest szybkie?

W rzeczywistości nie są. Nie tak wiele. Po prostu nie są wystarczająco wolne, aby większość z nas to zauważyła. W dawnych „powolnych dniach” było to znacznie bardziej zauważalne.

Nie są też odpowiednim narzędziem do każdego zadania - młotkiem .

Wieża
źródło
+1 Dziękuję za przypomnienie mi o tym konkretnym dziele sztuki ...
yannis
5

RegEx's są porównywalnie szybsze w pisaniu kodu, ponieważ większość bibliotek jest wynikiem tego, że wielu programistów spędza wiele lat optymalizując je, aby wydobyć z siebie każdą możliwą wydajność. Jednej osobie trudno jest powielić to w swoim własnym kodzie wyszukiwania.

Grandmaster B.
źródło
4
s / squeak / squeeze /?
Péter Török
4

Twoje podstawowe założenie jest błędne.

Wyrażenia regularne nie zawsze są szybsze niż proste wyszukiwanie. Wszystko zależy od kontekstu. Zależy to od złożoności wyrażenia, długości przeszukiwanego dokumentu i całego szeregu czynników.

Dzieje się tak, ponieważ wyrażenie regularne zostanie skompilowane w prosty analizator składni (co wymaga czasu). Tak więc, jeśli dokument jest mały, ten dodatkowy czas przeważy nad jakąkolwiek korzyścią. Ponadto, jeśli wyrażenie jest proste, to wyrażenie regularne nie da ci żadnej przewagi.

Jeśli wyrażenie jest złożone, a dokument wystarczająco duży, możesz uzyskać pewne korzyści. To, czy jest to wystarczająco istotne, aby uznać wyrażenie regularne za szybsze, będzie w dużej mierze zależeć od wysiłku, jaki chcesz włożyć w wyszukiwanie (również wyrażenia regularne mogą zawierać pewne optymalizacje, które może zapewnić biblioteka, których nie pomyślałbyś o sobie).

Próbuję powiedzieć, że nie ma ogólnej, ogólnej odpowiedzi. Jeśli masz określone wyrażenie (i znany rozmiar dokumentu), możesz powiedzieć, że uzyskasz odpowiedź tak / nie, czy wyrażenie będzie szybsze niż proste wyszukiwanie (i dlaczego).

Prawdziwą zaletą wyrażeń regularnych jest to, że gdy zrozumiesz, jak je pisać, możliwość wyrażenia złożonego wyszukiwania w zwięzły sposób. Ponieważ jest to uogólniona forma, możesz następnie budować narzędzia, które umożliwiają wyszukiwanie w sposób przydatny w ogólnym przypadku; zwykle jest co najmniej tak szybkie, jak proste wyszukiwanie (w przypadku dokumentów o minimalnym rozmiarze; w przypadku dokumentów mniejszych niż to nie ma znaczenia, ponieważ nawet jeśli jest wolniejszy, nadal jest wystarczająco szybki).

Martin York
źródło
1

Jest prawdopodobne, że w niektórych językach wysokiego poziomu (być może javascript) użycie biblioteki wyrażeń regularnych zaimplementowanych w języku niskiego poziomu (być może C) byłoby szybsze niż pisanie logiki parsera w języku wysokiego poziomu.

Możliwe - nie mam pojęcia, czy rzeczywiście tak się dzieje.

Steve Bennett
źródło
Niezłe! To też rozważałem. Ale przy dzisiejszych procesorach znacznie szybszych niż jego poprzednicy, mogę śmiało powiedzieć, że jeśli piszesz kod wydajnie, rzadko będziesz w stanie powiedzieć diff. Tak naprawdę nie jestem gaga w związku z szybszą hipotezą wyrażenia regularnego! ;-)
user3833732