Re: Usename regex
- From: Jesse Houwing <Jesse.houwing@xxxxxxxxxxxxxxxx>
- Date: Thu, 2 Aug 2007 10:36:12 +0000 (UTC)
Hello Jesse,
Hello Alexey,
On Aug 1, 11:42 pm, Jesse Houwing <Jesse.houw...@xxxxxxxxxxxxxxxx>Yours is probably faster I believe that, less alternatives for correct
wrote:
The problem is in the fact that it allows for excessiveJesse,
backtracking. Think of a string, preferably very long that contains
only alphanumeric characters, but end in a # sign. This regex will
try every combination of the first and the second part until all
options are exhausted. This can take quite a while.
I understand now why I forget about the (?) in my first post. I
misread your code. I thought you use the (?) in the third part of
your expression to find only one (_). I'm sorry I just can't believe
I was so inattentive.
Regarding backtracking. I understand now the difference between the
two expressions, and I believe what you are saying, but I did a small
quick test of how our expressions work for short and very long
strings in reality and it looks like there is no big difference.
Here's the result of the test
---------------------------------------------------------------------
-
------
Regular expression benchmark
----------------------------
Regular expressions : 2
Test strings : 3
Iterations : 10000
Total regex calls : (10000 * 3 * 2) = 60000
RE: ^([a-zA-Z0-9]+_?|_[a-zA-Z0-9]+|[a-zA-Z0-9]+_[a-zA-Z0-9]+)$
MS MAX AVG MIN DEV INPUT
61 16,759 0,0061 0,0031 0,1768 'aaaaa#'
101 16,778 0,0101 0,0067 0,1771 'some_realusername'
178 16,786 0,0178 0,0137 0,178
'verylongusernamestringwithnumbersandlet
tersandwithoutunderscoresymbolbutveryveryverylong1234verylong'
RE: ^([a-zA-Z0-9]+_?[a-zA-Z0-9]+)$
MS MAX AVG MIN DEV INPUT
51 3,251 0,0051 0,0039 0,038 'aaaaa#'
82 3,255 0,0082 0,007 0,038 'some_realusername'
161 3,263 0,0161 0,0142 0,047
'verylongusernamestringwithnumbersandlet
tersandwithoutunderscoresymbolbutveryveryverylong1234verylong'
---------------------------------------------------------------------
-
------
As you can see sometimes my expression is quicker :-)
The code of the benchmark tool is here
http://www.codinghorror.com/files/code/regexbenchmark.zip
I compiled it in .NET2 and ran without debugger. If I run the
benchmark 4-5 times very often I see that my expression has the best
reported score, even for a long strings. So, I would say that
^([a-zA-Z0-9]+_?[a-zA-Z0-9]+)$
is better, because it's shorter
strings. :) but have you tried a very long incorrect input? Something
like (the longer the better)
aaaaaaaaaaaavvvvvbbbbbbbbbbbbbbbbbbbbbbbeeeeeeeeeeeeeeeeeeeAAAAAAAAAAA
AAAA666666666666666666666666666666666666666666666&
If the textbox in question is limited to say 16 characters you'd
probably never trigger the problem, but a hacker could just bypass the
length of the textbox and supply a very very long string and if he'd
send such strings in quick succession he'd essentially cause a denial
of service.
There are some optimizations that are possible for thsi regex if
you'd want to try them. The enige will try the first option first, if
that fails it will try the second. Keeping that in mind, the order of
expressions is of importance. Say that you usually have no '_' in
usernames, but if they're there you mostly have them somewhere in
between. Then you'd have to change the order to improve performance.
^([a-zA-Z0-9]+(?:_[a-zA-Z0-9]+)?|[a-zA-Z0-9]+_|_[a-zA-Z0-9]+)$
Also my expression allows an underscore both at the start, the end and
in
between. Yours only covers the last option. I would probably rewrite
my expression
to this to make it do the same as your expression. It is almost as
short,
but does not allow excessive backtracking.
^[a-zA-Z0-9]+(_[a-zA-Z0-9]+)?$
And then there is the option to handle upper and lower case characters
in the character groups, or in a regexoption. I'm actually not sure
which is faster, but it's worth a try... Wrapping the whole expression
with (?i: ... ) should do the trick. all [a-zA-Z] can then be replaced
with just [a-z] ^(?i:....)$
And finally to suppress grouping & capturing we can improve
performance by replacing the normal ( ... ) with (?: ... ).
To optimize your expression further you could completely remove the (
... ) they have no use.
So a fair showdown of expressions would be:
Yours: ^[a-zA-Z0-9]+_?[a-zA-Z0-9]+$
Mine: ^[a-zA-Z0-9]+(?:_[a-zA-Z0-9]+)?$
Or with case insensitivity:
Yours: ^(?i:[a-z0-9]+_?[a-z0-9]+)$
Mine: ^(?i:[a-z0-9]+(?:_[a-z0-9]+)?)$
I ran it using the same tool you used on my Opteron 185 (2x2.6Ghz)
under Windows Vista x64. I made a small change to the code of the
benchmark though, the original benchmark takes the Compile hit in the
results. I did one call using the specific expression outside of the
loop so that the results can be compared more easily.
Input's used:
0
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
1 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", _
2 "aaaa", _
3
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa%",
_
4 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa%", _
5 "aaaa%", _
6
"aaaaaaaaaaaaaaaaaaaa_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
_
7 "aaaaaaaaaaaaaaaaaaaa_aaaaaaaaaaaaaaaaaaaaa", _
8 "aa_aa", _
9
"aaaaaaaaaaaaaaaaaaaa_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa%",
_
10 "aaaaaaaaaaaaaaaaaaaa_aaaaaaaaaaaaaaaaaaaaa%", _
11 "aa_aa%" _
Results:
Regular expression benchmark
----------------------------
Regular expressions : 4
Test strings : 12
Iterations : 10000
Total regex calls : (10000 * 12 * 4) = 480000
Pass 1, measure every regex as it runs (slower due to timing code)...
------------------------------------------
Regular expression library: System.Text.RegularExpressions
Total time taken: 58905
------------------------------------------
Pass 2, measure total time only..
------------------------------------------
Regular expression library: System.Text.RegularExpressions
RE: ^[a-zA-Z0-9]+_?[a-zA-Z0-9]+$
MS MAX AVG MIN DEV INPUT
110 0,365 0,011 0,0101 0,0073 '0'
145 0,387 0,0145 0,0134 0,0088 '1'
167 0,391 0,0167 0,0154 0,0095 '2'
17804 10,683 1,7804 1,6751 0,3004 '3'
18291 10,756 1,8291 1,7206 0,3042 '4'
18319 10,78 1,8319 1,7231 0,3046 '5'
18429 10,791 1,8429 1,7335 0,3055 '6'
18464 10,794 1,8464 1,7365 0,3058 '7'
18487 10,797 1,8487 1,7388 0,3059 '8'
18741 10,842 1,8741 1,7625 0,3079 '9'
18891 10,856 1,8891 1,7762 0,3129 '10'
18918 10,88 1,8918 1,7784 0,3135 '11'
RE: ^[a-zA-Z0-9]+(?:_[a-zA-Z0-9]+)?$
MS MAX AVG MIN DEV INPUT
107 0,229 0,0107 0,0101 0,0049 '0'
141 0,484 0,0141 0,0134 0,0076 '1'
163 0,562 0,0163 0,0154 0,0085 '2'
512 1,015 0,0512 0,0489 0,0166 '3'
585 1,022 0,0585 0,0559 0,018 '4'
611 1,025 0,0611 0,0584 0,0185 '5'
715 1,035 0,0715 0,0682 0,0204 '6'
749 1,038 0,0749 0,0715 0,0207 '7'
773 1,604 0,0773 0,0735 0,0258 '8'
1010 1,634 0,101 0,0961 0,0299 '9'
1072 1,64 0,1072 0,102 0,0304 '10'
1097 1,643 0,1097 0,1045 0,0305 '11'
RE: ^(?i:[a-z0-9]+_?[a-z0-9]+)$
MS MAX AVG MIN DEV INPUT
241 2,098 0,0241 0,0204 0,0231 '0'
299 2,108 0,0299 0,0254 0,0241 '1'
325 2,11 0,0325 0,0279 0,0242 '2'
34692 17,108 3,4692 3,0303 0,4154 '3'
35653 17,191 3,5653 3,113 0,4274 '4'
35694 17,195 3,5694 3,1163 0,4284 '5'
35932 17,215 3,5932 3,137 0,4298 '6'
35990 17,22 3,599 3,1417 0,4304 '7'
36018 17,223 3,6018 3,1443 0,4305 '8'
36505 17,29 3,6505 3,1867 0,4337 '9'
36782 17,493 3,6782 3,2107 0,438 '10'
36815 17,496 3,6815 3,2138 0,4387 '11'
RE: ^(?i:[a-z0-9]+(?:_[a-z0-9]+)?)$
MS MAX AVG MIN DEV INPUT
236 1,798 0,0236 0,0201 0,0195 '0'
291 1,811 0,0291 0,0251 0,0201 '1'
320 4,578 0,032 0,0274 0,0497 '2'
946 4,635 0,0946 0,0827 0,0546 '3'
1067 4,645 0,1067 0,093 0,0611 '4'
1097 4,648 0,1097 0,0958 0,0613 '5'
1333 4,669 0,1333 0,1162 0,0631 '6'
1388 4,674 0,1388 0,1212 0,0633 '7'
1415 4,677 0,1415 0,1235 0,0634 '8'
1791 4,711 0,1791 0,1576 0,0654 '9'
1890 4,989 0,189 0,1659 0,0814 '10'
1920 4,999 0,192 0,1687 0,0816 '11'
Total time taken: 58088
------------------------------------------
Press ENTER to continue...
I wouldn't have thought that case insensitivity would make such a big
difference. Learned something again today :).
My expression, without the case insensitivity is clearly the fastest:
RE: ^[a-zA-Z0-9]+(?:_[a-zA-Z0-9]+)?$
So I'd say this one is better, as it's only 3 characters longer than
yours, but much faster and without a possible DoS problem.
But as the original post didn't say that the underscore could only be
between alphanumeric characters. It said that there was one '_'
allowed in teh string (read anywhere in the string) my first
expression best covers the problem.
^(?:[a-zA-Z0-9]+(?:_[a-zA-Z0-9]+)?|[a-zA-Z0-9]+_|_[a-zA-Z0-9]+)$
Jesse
I tried my original expression based on the optimizations I did above and these are the results (and tried another variant which seems to be even better):
Regular expression benchmark
----------------------------
Regular expressions : 2
Test strings : 12
Iterations : 10000
Total regex calls : (10000 * 12 * 2) = 240000
Pass 1, measure every regex as it runs (slower due to timing code)...
------------------------------------------
Regular expression library: System.Text.RegularExpressions
Total time taken: 2601
------------------------------------------
Pass 2, measure total time only..
------------------------------------------
Regular expression library: System.Text.RegularExpressions
RE: ^(?:[a-zA-Z0-9]+(?:_[a-zA-Z0-9]+)?|[a-zA-Z0-9]+_|_[a-zA-Z0-9]+)$
MS MAX AVG MIN DEV INPUT
107 0,407 0,0107 0,0101 0,0072 '0'
142 0,412 0,0142 0,0134 0,0083 '1'
163 0,523 0,0163 0,0154 0,0093 '2'
676 4,552 0,0676 0,0634 0,0553 '3'
777 4,567 0,0777 0,0726 0,0634 '4'
805 4,569 0,0805 0,0754 0,0635 '5'
925 15,511 0,0925 0,0852 0,167 '6'
960 15,527 0,096 0,0886 0,1673 '7'
982 15,529 0,0982 0,0905 0,1673 '8'
1245 15,554 0,1245 0,1154 0,1682 '9'
1320 15,562 0,132 0,1224 0,1684 '10'
1347 15,565 0,1347 0,1249 0,1684 '11'
RE: ^(?:[a-zA-Z0-9]+(?:_[a-zA-Z0-9]*)?|_[a-zA-Z0-9]+)$
MS MAX AVG MIN DEV INPUT
112 3,757 0,0112 0,0101 0,0402 '0'
148 3,765 0,0148 0,0134 0,0412 '1'
169 3,767 0,0169 0,0154 0,0412 '2'
525 3,801 0,0525 0,0492 0,0476 '3'
599 3,809 0,0599 0,0562 0,0478 '4'
626 3,811 0,0626 0,0584 0,0494 '5'
737 4,931 0,0737 0,0687 0,0707 '6'
773 4,938 0,0773 0,0718 0,0714 '7'
796 4,941 0,0796 0,074 0,0715 '8'
1041 4,965 0,1041 0,0972 0,0735 '9'
1105 4,971 0,1105 0,1031 0,0741 '10'
1131 4,974 0,1131 0,1056 0,0744 '11'
Total time taken: 2037
------------------------------------------
Press ENTER to continue...
It cannot rival the simpler expression for speed, but it's coming close.
Appart from all this, my guess is that a simple string function would be even faster (and not even that hard to read) (C#). But if you want to have this clientside as well, you'll need to write a similar function in Javascript and maintain that too.
public bool IsCorrectName(string input)
{
bool underscoreFound = false;
foreach (char c in string input)
{
if (c >= 'A' && c<='Z'){ continue };
if (c >= 'a' && c<='z'){ continue };
if (c >= '0' && c<='9'){ continue };
if (c == '_' && !underscoreFound)
{
underscoreFound = true;
continue;
}
return false;
}
return true;
}
I haven't timed it. But I think there will be no contest here.
Jesse
.
- References:
- Re: Usename regex
- From: Jesse Houwing
- Re: Usename regex
- Prev by Date: RE: Enterprise Library number jumble
- Next by Date: Re: Strange doubt javascript:confirm
- Previous by thread: Re: Usename regex
- Next by thread: resx in dll
- Index(es):
Relevant Pages
|
