Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Say you have a document with an essay written. You want to parse this essay to only select certain words. Cool.

Is using a regular expression faster than parsing the file line by line and word by word looking for a match? If so, how does it work? How can you go faster than looking at each word?

share|improve this question
5  
You assume (implying zero evidence) that a regular expression will be quicker but you don't know why it is? Maybe you should reconsider your assumption then. –  pdr Nov 30 '11 at 4:22
2  
thus, the assumption. if i had evidence, it wouldn't be one, right? –  lazeR Nov 30 '11 at 4:27
3  
That's not the point. The point is what led you to that assumption... You don't need evidence for your questions, but you do need reasoning for your assumptions. –  Yannis Rizos Nov 30 '11 at 4:32
1  
err, aren't every character of input string just moving a state machine to next state. I don't see how anyone could get that operation slow... –  tp1 Nov 30 '11 at 4:56
1  
I'm not sure about quicker, but my main reason for using regular expressions is due to the elegance of complex matching patterns, you simply won't find a better way to articulate it in a coding environment. –  Mantorok Nov 30 '11 at 10:54
show 2 more comments

7 Answers

up vote 26 down vote accepted

How does it work?

Take a look at automata theory

In short, each regular expression has an equivalent finite automaton and can be compiled and optimized to a finite automaton. The involved algorithms can be found in many compiler books. These algorithms are used by unix programs like awk and grep. Most modern programming languages (Perl, Python, Ruby, Java (and JVM based languages), C#) do not use this approach. They use recursive backtracking approach, which compiles a regular expression into a tree or a sequence of constructs representing various sub-chunks of the regular expression. Most modern "regular expression" syntaxes offer backreferences which are outside the group of regular languages (they have no representation in finite automata), which are trivially implementable in recursive backtracking approach.

The optimization does usually yield a more efficient state machine. For example: consider aaaab|aaaac|aaaad, a normal programmer can get the simple but less efficient search implementation (comparing three strings separately) right in ten minutes; but realizing it is equivalent to aaaa[bcd], a better search can be done by searching first four 'a' then test the 5th character against [b,c,d]. The process of optimization was one of my compiler home work many years ago so I assume it is also in most modern regular expression engines.

On the other hand, state machines do have some advantage when they are accepting strings because they use more space compared to a "trivial implementation". Consider a program to un-escape quotation on SQL strings, that is: 1) starts and ends with single quotation marks; 2) single quotation marks are escaped by two consecutive single quotations. So: input ['a'''] should yield output [a']. With a state machine, the consecutive single quotation marks are handled by two states. These two states serve the purpose of remembering the input history such that each input character is processed exactly only once, as the following illustrated:

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

So, in my opinion, regular expression may be slower in some trivial cases, but usually faster than a manually crafted search algorithm, given the fact that the optimization cannot be reliably done by human.

(Even in trivial cases like searching a string, a smart engine can recognize the single path in the state map and reduce that part to a simple string comparison and avoid managing states.)

UPDATE

A particular engine from a framework/library may be slow because the engine does a bunch of other things a programmer usually don't need. Example: the Regex class in .NET create a bunch of objects including Match, Groups and Captures.

share|improve this answer
1  
This brings back fond memories, +1 –  Chris Nov 30 '11 at 13:53
    
I could not have said it better myself. The only thing I would add: Regular Expressions can also make up for lazy programmers. In the example you mentioned aaaab|aaaac|aaaad vs. aaaa[bcd]. It is worth explicitly stating that the two are mathematically equivalent and produce the same DFA, thus giving programmers more freedom to represent a regular expression in a way that makes sense (not that this is common practice, but...y'know)... –  Stargazer712 Nov 30 '11 at 23:30
    
Thanks, this actually made sense thanks to the automata class that i took –  lazeR Dec 1 '11 at 2:30
    
Is this an example of a trivial problem where regex is overkill?: stackoverflow.com/questions/18955099/… –  maythesource.com Sep 23 '13 at 9:03
add comment

Regular expressions just look fast because you have fast computers.

Back in the 1980's when 1 MIPS was a fast computer, regular expressions were a fairly big area of worry, concern and research because they were slow and ugly and compute intensive. Clever algorithm development followed and helped - but for all practical purposes these days you are seeing the miracle of fast machines papering over the cracks.

share|improve this answer
2  
If you are just looking for a single word both methods are the same (or regexp is slightly slower). But given a complex expression (and text of a reasonably large size) the regular expression will probably be faster than a simple search (assuming you write the simple search simply (you can always write a complex search that is as fast)). Now weather it is significant is too general a question and you will have to look at it on a case by case basis. –  Loki Astari Nov 30 '11 at 4:52
3  
-1. The theory of regular expression dates back to the 50's and was instrumental in creating lexical analyzers (and by extension, compilers). They create very efficient state machines that (provably) use the fewest number of states possible. The resulting state machines can match complex patterns much faster than anything you could write by hand. They look fast because they are fast. –  Stargazer712 Nov 30 '11 at 23:36
    
Might have missed my point a bit. They may be "fast" but thats all relative - there is still a bunch of work to do. Some of the other answers here bear reading as well. –  quickly_now Dec 4 '11 at 7:48
add comment

Why do you think they are quicker than searching the document?

There are some tricks you can do, eg. if you are searching for a 10letter word beginning with A and ending with B then if you find a A and the character 9 positions further on isn't B then you can skip some. see Knuth–Morris–Pratt algorithm

share|improve this answer
add comment

RegEx's are comparably faster to code you might write because most libraries are the result of many developers spending many years optimizing them to squeak out every last bit of performance possible. Its difficult for a single individual to duplicate that in their own search code.

share|improve this answer
    
s/squeak/squeeze/ ? –  Péter Török Nov 30 '11 at 8:07
add comment

What makes a regular expression fast?

Actually, they're not. Not that much. It's just that they're not slow enough for most of us to notice. Back in the 'old slow days, it was much more noticeable.

They're also not the right tool for every job - the hammer.

share|improve this answer
    
+1 Thanks for reminding me of that particular work of art... –  Yannis Rizos Nov 30 '11 at 4:34
add comment

Your basic premise is wrong.

Regular expressions are not always faster than a simple search. It all depends on context. It depends on the complexity of the expression, the length of the document being searched, and a whole host of factors.

What happens is that the regular expression will be compiled into a simple parser (which takes time). Thus, if the document is small, this extra time will outweigh any advantage. Also, if the expression is simple, then the regular expression will not give you any advantage.

If the expression is complex and the document large enough, then you can gain some benefit. Weather this is significant enough to consider regular expressions to be faster will depend a lot on how much effort you want to put into the search (also regular expressions may have some optimizations that a library could provide that you would not have thought of yourself).

What I am trying to say is that there is no generalized, blanket answer. If you had a specific expression (and a known document size), then you could say derive a yes/no answer of whether the expression will be quicker than a simple search (and why).

The real advantage of regular expressions is the ability to express a complex search in a simple manner (once you understand how to write the regular expression—some would claim it’s not that simple). Because it is a generalized form, you can then build tools that allow searches in a way that is useful in the general case; it is usually at least as fast as a simple search (on documents of minimum size; on documents smaller than this it would not matter since even if it is slower, it is still fast enough).

share|improve this answer
add comment

It is plausible that in some high-level languages (perhaps javascript), using a regex library implemented in a low-level language (perhaps C) would be faster than writing parser logic in the high-level language.

Plausible - I have no idea if this is ever actually the case.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.