Reversing strings

Today someone asked about reversing strings in the CF newsgroup.  He had found a snippet on the web that looked like this:

public static string StrRev(string s)
   if (s.Length == 1)
     return s;
return StrRev( s.Substring(1) ) + s.Substring(0,1);

Frightening recursion coupled with slow string access means really bad perf in something like this.  So it was suggested that he remove the recursion and try something like using StringBuilder.Append or Array.Reverse:

public static string StrRevArray( string s )
 char[] charArray;
 charArray = s.ToCharArray();
 Array.Reverse( charArray, 0, s.Length );
 return ( new string( charArray ) );

To me, this is missing the forest for the trees.  Why not be efficient and use pointers?  So I wrote a quick test, benchmarked it against the Array.Reverse version and normalized my results against the other posted results. Here’s my implementation:

public unsafe static string StrRevPtr(string s)
 int len = s.Length;

 char[] srcchars = s.ToCharArray();
 char[] destchars = new char[len];

 fixed(char *src = srcchars, dest = destchars)
   for(int i = 0 ; i < len ; i++)
     dest[len-i-1] = src[i];
 return new string(destchars);

And the normalized results (using the Compact Framework of course):

Array.Reverse: 114 seconds
StringBuilder.Append: 25 seconds
Indexer in StringBuilder: 20 seconds
Using pointers: 9 seconds

A case of not seeing the forest for the trees perhaps?  Just because it says “unsafe“ doesn’t mean “don’t use“.  If you’re a VB developer, sorry, you’ll have to live with poor perf here.

Of course you could save memory by just using a single char buffer and swapping the source array contents – it would be slower than what I propose above, but far more memory efficient.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s