Home Uncategorized More on string reversal!

    More on string reversal!

    519
    7

    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!

    Previous articleReversing a string in .NET
    Next articleScalar functions, inlining, and performance: An entertaining title for a boring post
    Adam Machanic helps companies get the most out of their SQL Server databases. He creates solid architectural foundations for high performance databases and is author of the award-winning SQL Server monitoring stored procedure, sp_WhoIsActive. Adam has contributed to numerous books on SQL Server development. A long-time Microsoft MVP for SQL Server, he speaks and trains at IT conferences across North America and Europe.

    7 COMMENTS

    1. 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);
      }

    2. Mladen:

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

    3. 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.

    4. 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.

    5. 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)

    Comments are closed.