somebody elsewhere wrote, in response to 
http://swtch.com/~rsc/regexp/regexp1.html
 > Try the .NET equivalent of this:
 > def scan(len):
 >     print re.match("a?" * len + "a" * len, "a" * len)

I'm surprised. It actually looks exponential.

http://msdn.microsoft.com/en-us/library/8zbs0h2f.aspx

http://msdn.microsoft.com/en-us/library/e347654k.aspx

I would have thought anyone going to the trouble of doing a bunch of caching 
and letting you compile it down to machine code would have picked an 
algorithm that's linear over one that's exponential.


Starting regex test
Length 5 took 2 miliseconds to run 10 times
Length 6 took 2 miliseconds to run 10 times
Length 7 took 2 miliseconds to run 10 times
Length 8 took 3 miliseconds to run 10 times
Length 9 took 4 miliseconds to run 10 times
Length 10 took 4 miliseconds to run 10 times
Length 11 took 6 miliseconds to run 10 times
Length 12 took 5 miliseconds to run 10 times
Length 13 took 7 miliseconds to run 10 times
Length 14 took 10 miliseconds to run 10 times
Length 15 took 15 miliseconds to run 10 times
Length 16 took 27 miliseconds to run 10 times
Length 17 took 51 miliseconds to run 10 times
Length 18 took 98 miliseconds to run 10 times
Length 19 took 190 miliseconds to run 10 times
Length 20 took 376 miliseconds to run 10 times
Length 21 took 757 miliseconds to run 10 times
Length 22 took 1485 miliseconds to run 10 times
Length 23 took 2955 miliseconds to run 10 times
Length 24 took 5933 miliseconds to run 10 times
Length 25 took 12006 miliseconds to run 10 times
Length 26 took 24206 miliseconds to run 10 times
Length 27 took 47463 miliseconds to run 10 times



         private static void TestRegEx()
         {
             Debug.WriteLine("Starting regex test");
             int loops = 10;
             for (int len = 5; len < 28; len++)
             {
                 string re = "";
                 string ma = "";
                 for (int i = 0; i < len; i++)
                 {
                     re += "a?"; ma += "a";
                 }
                 re += ma;
                 RegexOptions opt = RegexOptions.Compiled;
                 Regex matcher = new Regex(re, opt);
                 Stopwatch start = System.Diagnostics.Stopwatch.StartNew();
                 for (int j = 0; j < loops; j++)
                 {
                     bool match = matcher.IsMatch(ma);
  // Debug.WriteLine("Len=" + len + " j=" + j + " match=" + match);
                 }
                 Debug.WriteLine(
"Length " + len + " took " + start.ElapsedMilliseconds +
" miliseconds to run " + loops + " times");
                 start.Stop();
             }
         }

-- 
Darren New, San Diego CA, USA (PST)
    C# - a language whose greatest drawback
    is that its best implementation comes
    from a company that doesn't hate Microsoft.

Post a reply to this message