Jak faktycznie działają wyrażenia regularne?

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?

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.

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.

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

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 .

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.

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).

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.