THE SQL Server Blog Spot on the Web
Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search
Home Blogs Downloads   Opml View as RSS news feed in XML

Adam Machanic

Adam Machanic, Boston-based SQL Server developer, shares his experiences with programming, monitoring, and performance tuning SQL Server. And the occasional battle with the query optimizer.

More on string reversal!

In the last installment, I showed a potentially fastest method using Array.Reverse.

After finding and fixing a bug in method #3 posted in my last installment (it is, in fact, quite a bit faster than method #1 when you don't have a big huge bug in the code <g>) creating a new method, and hearing from Mladenp about a method he came up with, I decided that I should post another round of results.  So, here are the five methods I'm now testing:

        public static string Reverse1(string s)
        {
            StringBuilder sb = new System.Text.StringBuilder(s.Length);
            int i = s.Length;

            while (i-- > 0)
            {
                sb.Append(s[i]);
            }

            return sb.ToString();
        }

        public static string Reverse2(string s)
        {
            char[] rev = s.ToCharArray();
            Array.Reverse(rev);
            return (new string(rev));
        }

        public static string Reverse3(string s)
        {
            char[] charArray = s.ToCharArray();

            int i = charArray.Length;

            StringBuilder sb = new System.Text.StringBuilder(i);           

            while (i-- > 0)
            {
                sb.Append(charArray[i]);
            }

             return sb.ToString();
        }

        public static string Reverse4(string s)
        {
            char[] charArray = s.ToCharArray();

            int i = charArray.Length;
            int j = i-1;

            string[] outStr = new string[i];

            while (i-- > 0)
            {
                outStr[j - i] = charArray[i].ToString();
            }

            return String.Join("", outStr);
        }

        public static string Reverse5(string s)
        {
            char[] charArray = s.ToCharArray();
            int len = s.Length - 1;

            for (int i = 0; i < len; i++, len--)
            {
                charArray[i] ^= charArray[len];
                charArray[len] ^= charArray[i];
                charArray[i] ^= charArray[len];
            }

            return new string(charArray);
        }

Results (10000 iterations, 26-character string):

Reverse1: 106.767 ms
Reverse2: 12.752 ms
Reverse3: 61.902 ms
Reverse4: 87.963 ms
Reverse5: 12.15 ms

Winner, by a very small margin: Mladenp's XOR method!

Anyone else want to weigh in?  Submissions are open!

Published Monday, July 17, 2006 8:13 PM by Adam Machanic
Filed under: ,

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

Mladen said:

have you tried this one?

public string Reverse(string x)
{
   char[] charArray = new char[x.Length];
   int len = x.Length - 1;
   for (int i = 0; i <= len; i++)
       charArray[i] = x[len-i];
   return new string(charArray);
}
July 18, 2006 2:24 AM
 

Adam Machanic said:

Mladen:

Just tested it.  It falls halfway between methods 2 and 3 (2 being the 2nd fastest, after 5).

July 18, 2006 7:20 PM
 

Mladen said:

hmm... that's interesting...

everytime i try it that one was faster than XOR.
July 19, 2006 1:52 AM
 

Adam Machanic said:

How are you testing, and what are you using to get the timings?

I am simply running every method in a loop 10000 times:

for (int i = 0; i<10000; i++)
{
 string s1 = Reverse1("abcdefghijklmnopqrstuvwxyz");
 string s2 = Reverse2("abcdefghijklmnopqrstuvwxyz");
 string s3 = Reverse3("abcdefghijklmnopqrstuvwxyz");
 string s4 = Reverse4("abcdefghijklmnopqrstuvwxyz");
 string s5 = Reverse5("abcdefghijklmnopqrstuvwxyz");
 string s6 = Reverse6("abcdefghijklmnopqrstuvwxyz");
}

I'm getting the timings using VS's profiler, in instrumentation mode, and looking at the "inclusive of children" column to get the final reported times.

July 19, 2006 10:31 AM
 

Mladen said:

well i simply do it like this:
string testString = "1234567890hguidagnrruiasngilrenglirengilrenglaes";
DateTime dtStart = DateTime.Now;
for (int i = 0; i < 1000000; i++)
{
   Reverse1(testString);
}
DateTime dtEnd = DateTime.Now;
TimeSpan ts = dtEnd - dtStart;

dtStart = DateTime.Now;
for (int i = 0; i < 1000000; i++)
{
   Reverse2(testString);
}
dtEnd = DateTime.Now;
ts = dtEnd - dtStart;

public string Reverse1(string x)
{
   char[] charArray = new char[x.Length];
   int len = x.Length - 1;
   for (int i = 0; i <= len; i++)
       charArray[i] = x[len - i];
   return new string(charArray);
}

public string Reverse2(string str)
{
   // convert the string to char array
   char[] charArray = str.ToCharArray();
   int len = str.Length - 1;
   for (int i = 0; i < len; i++, len--)
   {
       charArray[i] ^= charArray[len];
       charArray[len] ^= charArray[i];
       charArray[i] ^= charArray[len];
   }
   return new string(charArray);
}

is there something wrong with this way that i'm not familiar with?

An average time i get is around 650 ms for reverse1 and 850 for reverse2.
It doesn't matter how many times i run it.
July 20, 2006 7:34 AM
 

Adam Machanic said:

The problem with that method is that it's "wall clock" time -- during the middle of invocation of one of the methods the GC could kick in, some other unrelated process might require a bunch of time, etc -- that will skew the results.  The profiler, AFAIK, shows only time spent actually doing your task, so you don't have all of the other noise and get more accurate results.

That said, I went ahead and tried this method and here are my results (note, I ran each method 2 million times -- I was unable to get consistent results otherwise):

Reverse1: 1892.7216 ms
Reverse2: 660.9504 ms
Reverse3: 1892.7216 ms
Reverse4: 4196.0336 ms
Reverse5: 490.7056 ms
Reverse6: 2042.9376 ms
Reverse7: 510.7344 ms

Note that Reverse5 is your XOR method and Reverse7 is your new method.  So at least on my box, XOR still wins.

Here is the code I used to loop:

           DateTime theStart = DateTime.Now;
           for (int i = 0; i < 1000000; i++)
           {
               string s1 = Reverse1("abcdefghijklmnopqrstuvwxyz");
               s1 = Reverse1(s1);
           }
           DateTime theEnd = DateTime.Now;
           TimeSpan ts = theEnd - theStart;
           Console.WriteLine(ts.TotalMilliseconds.ToString());

           theStart = DateTime.Now;
           for (int i = 0; i < 1000000; i++)
           {
               string s2 = Reverse2("abcdefghijklmnopqrstuvwxyz");
               s2 = Reverse2(s2);
           }
           theEnd = DateTime.Now;
           ts = theEnd - theStart;
           Console.WriteLine(ts.TotalMilliseconds.ToString());

... (repeat for each up to Reverse7)

July 20, 2006 11:55 AM
 

Mladen said:

Cool. thanx for explaining that.

In the end though... who needs to reverse a string 2 million times, right? :)))

If you haven't yet go take a look at how Greg Young did it.
It's in the comments:
http://weblogs.sqlteam.com/mladenp/archive/2006/03/19/9350.aspx
July 21, 2006 2:07 AM

Leave a Comment

(required) 
(required) 
Submit

About Adam Machanic

Adam Machanic is a Boston-based SQL Server developer, writer, and speaker. He focuses on large-scale data warehouse performance and development, and is author of the award-winning SQL Server monitoring stored procedure, sp_WhoIsActive. Adam has written for numerous web sites and magazines, including SQLblog, Simple Talk, Search SQL Server, SQL Server Professional, CoDe, and VSJ. He has also contributed to several books on SQL Server, including "SQL Server 2008 Internals" (Microsoft Press, 2009) and "Expert SQL Server 2005 Development" (Apress, 2007). Adam regularly speaks at conferences and training events on a variety of SQL Server topics. He is a Microsoft Most Valuable Professional (MVP) for SQL Server, a Microsoft Certified IT Professional (MCITP), and an alumnus of the INETA North American Speakers Bureau.

This Blog

Syndication
©2006-2012 SQLblog.comTM
Brought to you by Adam Machanic & Peter DeBetta
Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement