Regex optimization

[Chuck B]

In a C# Regex expression which would be faster when run against say 10,000
strings:

Regex(@"\d+/\d+/\d+ The quick brown fox.*");

or

Regex(@"\d+/\d+/\d+ The.*");

The reason I'm asking is that I'm not sure how Regex works internally and
it's not clear why one would be faster than the other.

[Stephany Young]

Try both tests and then you will know!
"Chuck B" <ch****@shc1.comwrote in message
news:Ou**************@TK2MSFTNGP05.phx.gbl...

In a C# Regex expression which would be faster when run against say 10,000
strings:

Regex(@"\d+/\d+/\d+ The quick brown fox.*");

or

Regex(@"\d+/\d+/\d+ The.*");

The reason I'm asking is that I'm not sure how Regex works internally and
it's not clear why one would be faster than the other.

[Chuck B]

Yes I will - but then that won't tell me much about what went on internally.

I was hoping that someone with knowledge of the Regex engine could help me
understand why one was better than the other.

Thanks for your help. Oh wait... nm... ;)
"Stephany Young" <noone@localhostwrote in message
news:em**************@TK2MSFTNGP03.phx.gbl...

Try both tests and then you will know!
"Chuck B" <ch****@shc1.comwrote in message
news:Ou**************@TK2MSFTNGP05.phx.gbl...

>In a C# Regex expression which would be faster when run against say
10,000 strings:

Regex(@"\d+/\d+/\d+ The quick brown fox.*");

or

Regex(@"\d+/\d+/\d+ The.*");

The reason I'm asking is that I'm not sure how Regex works internally and
it's not clear why one would be faster than the other.

[Kevin Spencer]

The Regex engine works by looping through the string one character at a
time, applying the rules of the test to each fragment. In some cases, it
may backtrack, depending on the rules. Therefore, the more rules there are
in the regular expression, the longer it will take. The rules in the regular
expression are defined by the characters in it.

--
HTH,

Kevin Spencer
Microsoft MVP

DSI PrintManager, Miradyne Component Libraries:
http://www.miradyne.net

"Chuck B" <ch****@shc1.comwrote in message
news:Ou**************@TK2MSFTNGP05.phx.gbl...

In a C# Regex expression which would be faster when run against say 10,000
strings:

Regex(@"\d+/\d+/\d+ The quick brown fox.*");

or

Regex(@"\d+/\d+/\d+ The.*");

The reason I'm asking is that I'm not sure how Regex works internally and
it's not clear why one would be faster than the other.

[Chris Shepherd]

Chuck B wrote:

Yes I will - but then that won't tell me much about what went on internally.

I was hoping that someone with knowledge of the Regex engine could help me
understand why one was better than the other.

Thanks for your help. Oh wait... nm... ;)

Trying it for yourself and seeing the results is a perfectly reasonable
answer.

While it may not allow you to recreate the source code, it certainly
will tell you which way is more efficient. Because your original regexes
were completely unequal, it's hard to say whether you could actually
learn anything about what is going on "internally" since in one instance
you'd get a LOT more hits than the other.

Assuming a somewhat normal dataset where some records have "The quick
brown fox" and more records have "The" in them, I'd suggest that it's
probably more work to return more results than it is simply to find
them, so #1 wins out. On 10,000 lines of "The quick brown fox" where the
returned values would be equal, I'd wager on the second regex being
faster (equal time spent returning values, less time spent searching).

Chris.

[Chuck B]

"Chris Shepherd" <ch**@nospam.chsh.cawrote in message
news:%2***************@TK2MSFTNGP03.phx.gbl...

Chuck B wrote:

>Yes I will - but then that won't tell me much about what went on
internally.

I was hoping that someone with knowledge of the Regex engine could help
me understand why one was better than the other.

Thanks for your help. Oh wait... nm... ;)

Trying it for yourself and seeing the results is a perfectly reasonable
answer.

I have to disagree here. Trying it for myself will give me numbers but not
understanding which is the untimate goal.

While it may not allow you to recreate the source code, it certainly will
tell you which way is more efficient. Because your original regexes were
completely unequal, it's hard to say whether you could actually learn
anything about what is going on "internally" since in one instance you'd
get a LOT more hits than the other.

Assuming a somewhat normal dataset where some records have "The quick
brown fox" and more records have "The" in them, I'd suggest that it's
probably more work to return more results than it is simply to find them,
so #1 wins out. On 10,000 lines of "The quick brown fox" where the
returned values would be equal, I'd wager on the second regex being faster
(equal time spent returning values, less time spent searching).

The fault here is mine for not explaining adequately what I wanted.

In the case above I'm looking for the special case where there is 1 match
per string for either Regex. For instance; the result of running both
examples above against "09/26/07 The quick brown fox ran away."

The date would probably take just as long for each regex. However, it seems
like it might be more efficient with the static characters to search for a
longer string than a shorter one (assuming that there was no match embedded
inside of another match). The reason for the increase is that the pointer
pointing to the head of the search would move a greater length after a
successful match.

[Chuck B]

Thanks Kevin.

I ran a test with both 10,000 iterations of the test string - "9/19/09 This
is a test. This is only a test of the quick brown fox. If this had been a
real quick brown fox it would have eaten yer toes." with the Regex
"\d+/\d+/\d+.*real.*" and "\d+/\d+/\d+.*this had been a real.*" and it turns
out that there's about a 3 microsecond difference with the shorter
expression being faster.

I'm guessing that rules that involve escape characters like \d, \w would
take longer to match due to the fact that there are more candidates to sort
thru.
"Kevin Spencer" <un**********@nothinks.comwrote in message
news:eO**************@TK2MSFTNGP03.phx.gbl...

The Regex engine works by looping through the string one character at a
time, applying the rules of the test to each fragment. In some cases, it
may backtrack, depending on the rules. Therefore, the more rules there are
in the regular expression, the longer it will take. The rules in the
regular expression are defined by the characters in it.

--
HTH,

Kevin Spencer
Microsoft MVP

DSI PrintManager, Miradyne Component Libraries:
http://www.miradyne.net

"Chuck B" <ch****@shc1.comwrote in message
news:Ou**************@TK2MSFTNGP05.phx.gbl...

>In a C# Regex expression which would be faster when run against say
10,000 strings:

Regex(@"\d+/\d+/\d+ The quick brown fox.*");

or

Regex(@"\d+/\d+/\d+ The.*");

The reason I'm asking is that I'm not sure how Regex works internally and
it's not clear why one would be faster than the other.

[Kevin Spencer]

Hi Chuck,

Actually, it's just a simple matter of more rules in the regular expression.

\d+/\d+/\d+ The quick brown fox.*
\d+/\d+/\d+ The.*

Note that each character represents a rule. "quick brown fox" is actually 15
rules, indicating specific characters that must match. So, the Regex engine
must test each successive character in the target string against each of
these characters/rules to ascertain a match before moving on. With the
wildcard (.*), only the newline character (1 character) must be looked for.

--
HTH,

Kevin Spencer
Microsoft MVP

DSI PrintManager, Miradyne Component Libraries:
http://www.miradyne.net
"Chuck B" <ch****@shc1.comwrote in message
news:OE**************@TK2MSFTNGP03.phx.gbl...

Thanks Kevin.

I ran a test with both 10,000 iterations of the test string - "9/19/09
This is a test. This is only a test of the quick brown fox. If this had
been a real quick brown fox it would have eaten yer toes." with the Regex
"\d+/\d+/\d+.*real.*" and "\d+/\d+/\d+.*this had been a real.*" and it
turns out that there's about a 3 microsecond difference with the shorter
expression being faster.

I'm guessing that rules that involve escape characters like \d, \w would
take longer to match due to the fact that there are more candidates to
sort thru.
"Kevin Spencer" <un**********@nothinks.comwrote in message
news:eO**************@TK2MSFTNGP03.phx.gbl...

>The Regex engine works by looping through the string one character at a
time, applying the rules of the test to each fragment. In some cases, it
may backtrack, depending on the rules. Therefore, the more rules there
are in the regular expression, the longer it will take. The rules in the
regular expression are defined by the characters in it.

--
HTH,

Kevin Spencer
Microsoft MVP

DSI PrintManager, Miradyne Component Libraries:
http://www.miradyne.net

"Chuck B" <ch****@shc1.comwrote in message
news:Ou**************@TK2MSFTNGP05.phx.gbl...

>>In a C# Regex expression which would be faster when run against say
10,000 strings:

Regex(@"\d+/\d+/\d+ The quick brown fox.*");

or

Regex(@"\d+/\d+/\d+ The.*");

The reason I'm asking is that I'm not sure how Regex works internally
and it's not clear why one would be faster than the other.