2

I need to do a search for people who are violating our "don't use social security numbers in your data" rule and need to know if there are performance differences (and why) between the two lines below.

Thanks.

[0-9]{3}-[0-9]{2}-[0-9]{4}

vs

\d\d\d-\d\d-\d\d\d\d


Requested Details:
engine: removed to stop confusion in tagging

4
  • 1
    You can easily compare the performance of these two. What results do you have from doing the comparison?
    – S.Lott
    Feb 18, 2009 at 15:04
  • I was hoping to get some good theory on building efficient searches. But, if no one gives me that I'll run and post.
    – Keng
    Feb 18, 2009 at 15:14
  • You didn't mention what tool/language will be used to run the regular expression. The implementation of the specific platform could change the balance between the two options. Please clarify in your question.
    – JohnFx
    Feb 18, 2009 at 15:21
  • it will be run on QuickMacros and/or RegexBuddy Grep both of which use the Perl engine. The command on XP Pro the targets on Win2003 server.
    – Keng
    Feb 18, 2009 at 17:02

10 Answers 10

9

I think you would see very negligible differences in performance. Use the first one, as it is easier to read at a glance. Once the Regex is compiled (if you are compiling it before using it for reuse purposes), it would not matter anyway.

Don't optimize until you need to optimize.

8

Performance aside, I recently found out that \d and [0-9] are not identical, because there are more than just 10 digits. Therefore, the second version might yield more false positives.

2
  • Yeah, I saw that too 8O) hopefully there's not a way for our people to even enter them in the first place though.
    – Keng
    Feb 18, 2009 at 15:10
  • 1
    I'm doubting that anyone in Turkey will provide their social security number in the first place, though. :-)
    – Ken White
    Feb 18, 2009 at 15:31
3

The performance difference, if any, will be absolutely neglible. You're likely to be optimizing wrong part of your application.

3

The performance difference should be negligible. On an unrelated note, if the data you're dealing with are anything like the stuff I see, it might be useful to expand the search by making the dashes optional:

\b\d{3}-?\d{2}-?\d{4}\b

Update: Good point, Keng. The word-boundary trick is really useful, so I'd definitely include it in a first pass.

1
  • yeah, I was thinking about that but because of all the other numbers that could be there I wanted to try and avoid 9 numbers in a row...but then if i used \b\d{9}\b that might help limit the false positives....hmmmm.
    – Keng
    Feb 18, 2009 at 15:16
1

As with any performance question, the answer is to benchmark test it with your own data and find out. Post the results with some sample data, because this is a good question.

1
  • I was hoping to get some good theory on building efficient searches. But, if no one gives me that I'll run and post.
    – Keng
    Feb 18, 2009 at 15:06
1

This Ruby script says the first is marginally slower, but I would expect the differences on any engine to be negligible.

require 'benchmark'
include Benchmark

def random_ssn
  format "%03d-%02d-%04d", rand(1000), rand(100), rand(10000)
end

bm do |x|
  x.report("range") { 100_000.times { /[0-9]{3}-[0-9]{2}-[0-9]{4}/ =~ random_ssn } }
  x.report("digit") { 100_000.times { /\d\d\d-\d\d-\d\d\d\d/       =~ random_ssn } }
end

Results:

      user     system      total        real
range  1.080000   0.030000   1.110000 (  1.245579)
digit  0.980000   0.030000   1.010000 (  1.149390)
2
  • Your benchmark uses data that will always trigger. With the OP's data, a match will be the odd one out.
    – innaM
    Feb 18, 2009 at 15:33
  • Agree, but that is trivially remedied.
    – jcrossley3
    Feb 18, 2009 at 15:35
1

Seconding the comment that this is not likely to be the performance bottleneck -- compared to I/O, etc., the difference is not likely to be measurable.

Having said that -- if you're concerned, measure it, don't guess.

2
  • I was hoping to get some good theory on building efficient searches. But, if no one gives me that I'll run and post.
    – Keng
    Feb 18, 2009 at 15:50
  • egad...I think it might be good to figure out 'on paper' how much plutonium to use before building the bomb...<8O() also, I need to avoid building it in the worst way possible (). Two words for you "catastrophic backtracking" regular-expressions.info/catastrophic.html
    – Keng
    Feb 18, 2009 at 17:20
1

There are better optimization available apart from what you note :

Social security number cannot start from number greater than 772

So that instantly reduces your match group , now you can :

[0-7][0-9]{2}-[0-9]{2}-[0-9]{4}

I guess what I'm trying to say is that optimization need not be just technical.

EDIT

Changed the regex as according to comment. Thanks David!

3
  • Should be <code>[0-7][0-9]{2}-[0-9]{2}-[0-9]{4}</code> or else it won't match 580-...
    – David
    Feb 18, 2009 at 15:45
  • this is what Regex Buddy says to use. \b(?!000)(?!666)(?:[0-6]\d{2}|7(?:[0-356]\d|7[012]))[- ](?!00)\d{2}[- ](?!0000)\d{4}\b
    – Keng
    Feb 18, 2009 at 15:48
  • That's the highest number they've allocated up until now. I don't think there's anything guaranteeing that won't change in the future.
    – Kibbee
    Feb 18, 2009 at 17:36
1

Of course the performance of the two expressions depends on the implementation of the regex engine you are using. The difference should be small, so don't optimize until you see it as a bottleneck.

Here is a little performance comparison, using perl 5.8.3 and a sample of 8MB of random data (digits, dashes, spaces):

time perl -ne 'if (/\d\d\d-\d\d-\d\d\d\d/) {print "."}' < numbers.txt
[output omitted]
real    0m0.143s
user    0m0.136s
sys     0m0.007s

time perl -ne 'if (/[0-9]{3}-[0-9]{2}-[0-9]{4}/) {print "."}' < numbers.txt
[output omitted]
real    0m0.166s
user    0m0.160s
sys     0m0.006s

So the first is actually a tiny bit faster (this is consistent across several calls).

3
  • This is consistent with the ruby results, too.
    – jcrossley3
    Feb 18, 2009 at 15:36
  • I'd have to check (I'm at a different machine now), but I think 5.8 Feb 18, 2009 at 19:13
  • "This is perl, v5.8.3 built for x86_64-linux-thread-multi" I also edited my answer to include the version. Feb 19, 2009 at 15:21
1

I just tested this in .NET with the benchmark feature of Regex Hero.

Surprisingly the first expression is faster, albeit only marginally so. I performed 500,000 iterations on a valid social security number and here are the results:

1.547 seconds - [0-9]{3}-[0-9]{2}-[0-9]{4}

1.844 seconds - \d\d\d-\d\d-\d\d\d\d

I tested each one 3 times to make sure the benchmark was accurate. It's funny that the result in .NET is the exact opposite of the results in Ruby and Perl.

2
  • wow...I wouldn't have thought that (.Net vs Perl/Ruby). Does Perl and Ruby use the same RX engine? That might explain why those two are the same.
    – Keng
    Aug 18, 2009 at 12:55
  • I don't think so. Looks like Ruby has its own regex engine. In fact all 3 use the same basic syntax as Perl but each engine is different. Aug 18, 2009 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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