views:

13918

answers:

16

I've just had to write a string reverse function in C# 2.0 (i.e. LINQ not available) and came up with this:

public string Reverse(string text)
{
    char[] cArray = text.ToCharArray();
    string reverse = String.Empty;
    for (int i = cArray.Length - 1; i > -1; i--)
    {
        reverse += cArray[i];
    }
    return reverse;
}

Personally I'm not crazy about the function and am convinced that there's a better way to do it. Is there?

A: 

here's my approach:

private string Reverse(string input)
{
    Stack<char> resultStack = new Stack<char>();
    foreach (char c in input)
    {
        resultStack.Push(c);
    }

    StringBuilder sb = new StringBuilder();
    while (resultStack.Count > 0)
    {
        sb.Append(resultStack.Pop());
    }
    return sb.ToString();
}

Edit: Ok, I ran the various approaches to the profiler, using the string "2fd4e1c67a2d28fced849ee1bb76e7391b93eb12" and 10.000 Reversals, counting "Time With Children (ms)". And yes, i know that there is no Reverse4, because it was a duplicate. Ran the test 3 times, results did not fluctuate too much for me. So yes, my approach sucks by a factor of 10, so i'll change my function in my code now :-)

Reverse1: 157,508ms

Reverse2: 63,133ms

Reverse5: 35,975ms

Reverse6: 3,710ms

Reverse7: 245,391ms

Linq approach: 64,325ms (Changed Target Framework from 2.0 to 3.5 for this)

Michael Stum
I haven't profiled it though, one possible performance optimization could be replacing the while with a simple for-loop, so that resultStack.Count only needs to be accessed once (int limit = resultStack.count, for(int i = 0; i<limit; i++)) Needs profiling though.
Michael Stum
What is the difference between Reverse3 and Reverse6? The have the same code
aku
I'm stupid, Reverse3 actually links to the "missing" Reverse4. Removed it now
Michael Stum
+2  A: 

Have a look at the wikipedia entry here. They implement the String.Reverse extension method. This allows you to write code like this:

string s = "olleh";
s.Reverse();

They also use the ToCharArray/Reverse combination that other answers to this question suggest. The source code looks like this:

public static string Reverse(this string input)
{
    char[] chars = input.ToCharArray();
    Array.Reverse(chars);
    return new String(chars);
}
Mike Thompson
That's wonderful, except extension methods weren't introduced in c# 2.0.
Kobi
+8  A: 

Firstly you don't need to call ToCharArray as a string can already be indexed as a char array, so this will save you an allocation.

The next optimisation is to use a StringBuilder to prevent unnecessary allocations (as strings are immutable, concatenating them makes a copy of the string each time). To further optimise this we pre-set the length of the StringBuilder so it won't need to expand its buffer.

public string Reverse(string text)
{
    if (string.IsNullOrEmpty(text))
    {
        return text;
    }

    StringBuilder builder = new StringBuilder(text.Length);
    for (int i = text.Length - 1; i >= 0; i--)
    {
        builder.Append(text[i]);
    }

    return builder.ToString();
}

Edit: Performance Data

I tested this function and the function using Array.Reverse with the following simple program, where Reverse1 is one function and Reverse2 is the other:

static void Main(string[] args)
{
    var text = "abcdefghijklmnopqrstuvwxyz";

    // pre-jit
    text = Reverse1(text); 
    text = Reverse2(text);

    // test
    var timer1 = Stopwatch.StartNew();
    for (var i = 0; i < 10000000; i++)
    {
        text = Reverse1(text);
    }

    timer1.Stop();
    Console.WriteLine("First: {0}", timer1.ElapsedMilliseconds);

    var timer2 = Stopwatch.StartNew();
    for (var i = 0; i < 10000000; i++)
    {
        text = Reverse2(text);
    }

    timer2.Stop();
    Console.WriteLine("Second: {0}", timer2.ElapsedMilliseconds);

    Console.ReadLine();
}

It turns out that for short strings the Array.Reverse method is around twice as quick as the one above, and for longer strings the difference is even more pronounced. So given that the Array.Reverse method is both simpler and faster I'd recommend you use that rather than this one. I leave this one up here just to show that it isn't the way you should do it (much to my surprise!)

Greg Beech
Wouldn't storing text.Length in a variable give a little more speed as you are referencing this via an object?
David Robbins
+27  A: 
public static string Reverse( string s )
{
    char[] charArray = s.ToCharArray();
    Array.Reverse( charArray );
    return new string( charArray );
}

I think the above works not tested, although the stringbuilder class may also have a reverse function I haven't checked that though.

PeteT
I've marked this one as the correct answer because it is the fastest and was the first posted with this solution. There is some great material to learn from in the other replies to this question.
Guy
I don't mean to nitpick (note my post is a community wiki) but this is not really the correct answer, 1. It has no mention of unicode 2. It has no null check. 3. Xor can be faster sometimes.
Sam Saffron
sambo99: It doesn't need to mention unicode: chars in C# are unicode characters, not bytes. Xor may be faster, but apart from being far less readable, that may even be what Array.Reverse() uses internally.
Nick Johnson
@Arachnid: Actually, chars in C# are UTF-16 code units; it takes two of them to represent a supplementary character. See http://www.jaggersoft.com/csharp_standard/9.4.1.htm.
Bradley Grainger
Yeah sambo99 I suppose you are correct but it's a pretty rare case to use UTF-32. And XOR is only faster for a very small range of values, the correct answer would be to implement different methods for different lengths I suppose. But this is clear and concise which is a benefit in my opinion.
PeteT
I use this as one of the many brain teaser's when we screen interns. Thanks!
PhantomTypist
Unicode control characters makes this method useless for non latin character sets. See Jon Skeet explanation, using a sock puppet: http://msmvps.com/blogs/jon_skeet/archive/2009/11/02/omg-ponies-aka-humanity-epic-fail.aspx (1/4 the way down), or the video: http://vimeo.com/7516539
Callum Rogers
@Callum Thanks for that I wasn't aware of the additional complexities of unicode control characters. They seem to be a pain.
PeteT
Hope you don't encounter any surrogates or combining characters.
dalle
+38  A: 

This is turning out to be a surprisingly tricky question.

I would recommend using Array.Reverse for most cases as it is coded natively and it is very simple to maintain and understand.

It seems to outperform StringBuilder in all the cases I tested.

public string Reverse(string text)
{
   if (text == null) return null;

   // this was posted by petebob as well 
   char[] array = text.ToCharArray();
   Array.Reverse(array);
   return array;
}

There is a second approach that can be faster for certain string lengths which uses Xor.

    public static string ReverseXor(string s)
    {
        if (s == null) return null;
        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);
    }

Note If you want to support the full Unicode UTF16 charset read this. And use the implementation there instead. It can be further optimized by using one of the above algorithms and running through the string to clean it up after the chars are reversed.

Here is a performance comparison between the StringBuilder, Array.Reverse and Xor method.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace ConsoleApplication4
{
    class Program
    {
        delegate string StringDelegate(string s);

        static void Benchmark(string description, StringDelegate d, int times, string text)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int j = 0; j < times; j++)
            {
                d(text);
            }
            sw.Stop();
            Console.WriteLine("{0} Ticks {1} : called {2} times.", sw.ElapsedTicks, description, times);
        }

        public static string ReverseXor(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);
        }

        public static string ReverseSB(string text)
        {
            StringBuilder builder = new StringBuilder(text.Length);
            for (int i = text.Length - 1; i >= 0; i--)
            {
                builder.Append(text[i]);
            }
            return builder.ToString();
        }

        public static string ReverseArray(string text)
        {
            char[] array = text.ToCharArray();
            Array.Reverse(array);
            return (new string(array));
        }

        public static string StringOfLength(int length)
        {
            Random random = new Random();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < length; i++)
            {
                sb.Append(Convert.ToChar(Convert.ToInt32(Math.Floor(26 * random.NextDouble() + 65))));
            }
            return sb.ToString();
        }

        static void Main(string[] args)
        {

            int[] lengths = new int[] {1,10,15,25,50,75,100,1000,100000};

            foreach (int l in lengths)
            {
                int iterations = 10000;
                string text = StringOfLength(l);
                Benchmark(String.Format("String Builder (Length: {0})", l), ReverseSB, iterations, text);
                Benchmark(String.Format("Array.Reverse (Length: {0})", l), ReverseArray, iterations, text);
                Benchmark(String.Format("Xor (Length: {0})", l), ReverseXor, iterations, text);

                Console.WriteLine();    
            }

            Console.Read();
        }
    }
}

Here are the results:

26251 Ticks String Builder (Length: 1) : called 10000 times.
33373 Ticks Array.Reverse (Length: 1) : called 10000 times.
20162 Ticks Xor (Length: 1) : called 10000 times.

51321 Ticks String Builder (Length: 10) : called 10000 times.
37105 Ticks Array.Reverse (Length: 10) : called 10000 times.
23974 Ticks Xor (Length: 10) : called 10000 times.

66570 Ticks String Builder (Length: 15) : called 10000 times.
26027 Ticks Array.Reverse (Length: 15) : called 10000 times.
24017 Ticks Xor (Length: 15) : called 10000 times.

101609 Ticks String Builder (Length: 25) : called 10000 times.
28472 Ticks Array.Reverse (Length: 25) : called 10000 times.
35355 Ticks Xor (Length: 25) : called 10000 times.

161601 Ticks String Builder (Length: 50) : called 10000 times.
35839 Ticks Array.Reverse (Length: 50) : called 10000 times.
51185 Ticks Xor (Length: 50) : called 10000 times.

230898 Ticks String Builder (Length: 75) : called 10000 times.
40628 Ticks Array.Reverse (Length: 75) : called 10000 times.
78906 Ticks Xor (Length: 75) : called 10000 times.

312017 Ticks String Builder (Length: 100) : called 10000 times.
52225 Ticks Array.Reverse (Length: 100) : called 10000 times.
110195 Ticks Xor (Length: 100) : called 10000 times.

2970691 Ticks String Builder (Length: 1000) : called 10000 times.
292094 Ticks Array.Reverse (Length: 1000) : called 10000 times.
846585 Ticks Xor (Length: 1000) : called 10000 times.

305564115 Ticks String Builder (Length: 100000) : called 10000 times.
74884495 Ticks Array.Reverse (Length: 100000) : called 10000 times.
125409674 Ticks Xor (Length: 100000) : called 10000 times.

It seems that Xor can be faster for short strings.

Sam Saffron
That doesn't return a string - you need to wrap this in a call to "new String(...)"
Greg Beech
BTW .. I just had a look at the implementation of Array.Reverse, and its done naitively for chars ... it should be much faster than the StringBuilder option.
Sam Saffron
How nice of you, Greg, to halp Sambo arrive at a better solution instead of down-voting him.
DOK
@dok1 - don't mention it :)@sambo99 - now I'm intrigued, will have to whip out a code profiler tomorrow and have a look!
Greg Beech
lol - now it's not returning a string again :)
Greg Beech
Good post, I think I would stick with my answer Array.Reverse not just because it seems to have good performance across string lengths but also because it is concise in the code. lets face it maintenance is half the problem. Also whats the performance penalty of all those using statements.
PeteT
I've added an in-place reverse with pointers down below if you're interested. I didn't want to add it to this post as it's something you should never ever do, just for curiosity's sake.
Greg Beech
These methods don't handle strings containing characters outside of the Base Multilingual Plane, i.e., Unicode characters >= U+10000 that are represented with two C# chars. I've posted an answer that handles such strings correctly.
Bradley Grainger
+2  A: 

"Better way" depends on what is more important to you in your situation, performance, elegance, maintainability etc.

Anyway, here's an approach using Array.Reverse:

string inputString="The quick brown fox jumps over the lazy dog.";
char[] charArray = inputString.ToCharArray(); 
Array.Reverse(charArray); 

string reversed = new string(charArray);
Ash
+3  A: 

Try using Array.Reverse


public string Reverse(string str)
{
    char[] array = str.ToCharArray();
    Array.Reverse(array);
    return new string(array);
}
Mike Two
This is incredibly fast.
Michael Stum
+2  A: 

Had to submit a recursive example:

private static string Reverse(string str)
{
    if (str.Length == 1)
        return str;
    else
        return str[str.Length - 1] + Reverse(str.Substring(0, str.Length - 1));
}
JPrescottSanders
+2  A: 

Sorry for long post, but this might be interesting

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        public static string ReverseUsingArrayClass(string text)
        {
            char[] chars = text.ToCharArray();
            Array.Reverse(chars);
            return new string(chars);
        }

        public static string ReverseUsingCharacterBuffer(string text)
        {
            char[] charArray = new char[text.Length];
            int inputStrLength = text.Length - 1;
            for (int idx = 0; idx <= inputStrLength; idx++) 
            {
                charArray[idx] = text[inputStrLength - idx];                
            }
            return new string(charArray);
        }

        public static string ReverseUsingStringBuilder(string text)
        {
            if (string.IsNullOrEmpty(text))
            {
                return text;
            }

            StringBuilder builder = new StringBuilder(text.Length);
            for (int i = text.Length - 1; i >= 0; i--)
            {
                builder.Append(text[i]);
            }

            return builder.ToString();
        }

        private static string ReverseUsingStack(string input)
        {
            Stack<char> resultStack = new Stack<char>();
            foreach (char c in input)
            {
                resultStack.Push(c);
            }

            StringBuilder sb = new StringBuilder();
            while (resultStack.Count > 0)
            {
                sb.Append(resultStack.Pop());
            }
            return sb.ToString();
        }

        public static string ReverseUsingXOR(string text)
        {
            char[] charArray = text.ToCharArray();
            int length = text.Length - 1;
            for (int i = 0; i < length; i++, length--)
            {
                charArray[i] ^= charArray[length];
                charArray[length] ^= charArray[i];
                charArray[i] ^= charArray[length];
            }

            return new string(charArray);
        }


        static void Main(string[] args)
        {
            string testString = string.Join(";", new string[] {
                new string('a', 100), 
                new string('b', 101), 
                new string('c', 102), 
                new string('d', 103),                                                                   
            });
            int cycleCount = 100000;

            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            for (int i = 0; i < cycleCount; i++) 
            {
                ReverseUsingCharacterBuffer(testString);
            }
            stopwatch.Stop();
            Console.WriteLine("ReverseUsingCharacterBuffer: " + stopwatch.ElapsedMilliseconds + "ms");

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < cycleCount; i++) 
            {
                ReverseUsingArrayClass(testString);
            }
            stopwatch.Stop();
            Console.WriteLine("ReverseUsingArrayClass: " + stopwatch.ElapsedMilliseconds + "ms");

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < cycleCount; i++) 
            {
                ReverseUsingStringBuilder(testString);
            }
            stopwatch.Stop();
            Console.WriteLine("ReverseUsingStringBuilder: " + stopwatch.ElapsedMilliseconds + "ms");

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < cycleCount; i++) 
            {
                ReverseUsingStack(testString);
            }
            stopwatch.Stop();
            Console.WriteLine("ReverseUsingStack: " + stopwatch.ElapsedMilliseconds + "ms");

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < cycleCount; i++) 
            {
                ReverseUsingXOR(testString);
            }
            stopwatch.Stop();
            Console.WriteLine("ReverseUsingXOR: " + stopwatch.ElapsedMilliseconds + "ms");            
        }
    }
}

Results:

  • ReverseUsingCharacterBuffer: 346ms
  • ReverseUsingArrayClass: 87ms
  • ReverseUsingStringBuilder: 824ms
  • ReverseUsingStack: 2086ms
  • ReverseUsingXOR: 319ms
aku
I added a similar comparison in my post, its a community wiki so you should be able to edit. The performance really depends on the length of the string as well as the algorithm, it would be interesting to graph it. I still think Array.Reverse will be fastest in all cases ...
Sam Saffron
"will be fastest in all cases" when magical TrySZReverse function (it's used in Reverse implementation) fails, Array.Reverse fallbacks to simple implementation involving boxing, so my method will win. However I don't know what is a condition to make TrySZReverse fail.
aku
Turns out its not fastest in all cases :), I updated my post. This still needs to be tested with unicode for both correctness and speed.
Sam Saffron
+3  A: 

If you want to play a really dangerous game, then this is by far the fastest way there is (around four times faster than the Array.Reverse method). It's an in-place reverse using pointers.

Note that I really do not recommend this for any use, ever (have a look here for some reasons why you should not use this method), but it's just interesting to see that it can be done, and that strings aren't really immutable once you turn on unsafe code.

public static unsafe string Reverse(string text)
{
    if (string.IsNullOrEmpty(text))
    {
        return text;
    }

    fixed (char* pText = text)
    {
        char* pStart = pText;
        char* pEnd = pText + text.Length - 1;
        for (int i = text.Length / 2; i >= 0; i--)
        {
            char temp = *pStart;
            *pStart++ = *pEnd;
            *pEnd-- = temp;
        }

        return text;
    }
}
Greg Beech
Im pretty sure this will return incorrect results for utf16 strings, it is really asking trouble :)
Sam Saffron
I never tested this but I like what you've done here.
Guy
Hi you should link to this post on this http://stackoverflow.com/questions/229346/why-should-i-never-use-an-unsafe-block-to-modify-a-string , as I said before this is really asking for trouble ...
Sam Saffron
This may be completely evil and ill-advised (as you yourself concede), but there's still a high-performance way to reverse a string using `unsafe` code that *isn't* evil and *still* beats `Array.Reverse` in many cases. Take a look at my answer.
Dan Tao
+9  A: 

If the string contains Unicode data (strictly speaking, non-BMP characters) the other methods that have been posted will corrupt it, because you cannot swap the order of high and low surrogate code units when reversing the string. (More information about this can be found on my blog.)

The following code sample will correctly reverse a string that contains non-BMP characters, e.g., "\U00010380\U00010381" (Ugaritic Letter Alpa, Ugaritic Letter Beta).

public static string Reverse(this string input)
{
    if (input == null)
     throw new ArgumentNullException("input");

    // allocate a buffer to hold the output
    char[] output = new char[input.Length];
    for (int outputIndex = 0, inputIndex = input.Length - 1; outputIndex < input.Length; outputIndex++, inputIndex--)
    {
     // check for surrogate pair
     if (input[inputIndex] >= 0xDC00 && input[inputIndex] <= 0xDFFF &&
      inputIndex > 0 && input[inputIndex - 1] >= 0xD800 && input[inputIndex - 1] <= 0xDBFF)
     {
      // preserve the order of the surrogate pair code units
      output[outputIndex + 1] = input[inputIndex];
      output[outputIndex] = input[inputIndex - 1];
      outputIndex++;
      inputIndex--;
     }
     else
     {
      output[outputIndex] = input[inputIndex];
     }
    }

    return new string(output);
}
Bradley Grainger
chars in C# are not bytes, they're actual characters. Thus, all of this is totally unnecessary.
Nick Johnson
Actually, chars in C# are 16-bit UTF-16 code units; a supplementary character is encoded using two of them, so this is necessary,
Bradley Grainger
For details, see §9.4.1.2 of the C# Language Specification: http://www.jaggersoft.com/csharp_standard/9.4.1.htm
Bradley Grainger
It seems like System.String really ought to expose a HereBeDragons property for strings that contain Unicode supplementary characters.
Robert Rossney
A: 

Before I discovered that everyone was posting their test results to this thread I wrote this up on my blog. Essentially the results of my tests on 10 and 500 character strings show that the Array.Reverse() function wins the game and that's why I've marked this one as the correct answer.

Much obliged to everyone for helping me with this. You guys rock!

Guy
Make sure you use a Stopwatch for your timings, it uses a high resolution time, also make sure you include the Xor method. Also you should mention something about unicode and correctness.
Sam Saffron
A: 

Is there a way to reverse a string without using arrays? maybe using substrings? Also, what exactly does the for loop of eg. for (int i = 0, i>0, i++) do? lastly, how do you output text within the same textbox on the second line?

A: 

public string rev(string str) { if (str.Length <= 0) return string.Empty; else return str[str.Length-1]+ rev(str.Substring(0,str.Length-1));

    }
Saeed
+1  A: 

Greg Beech posted an unsafe option that is indeed as fast as it gets (it's an in-place reversal); but, as he indicated in his answer, it's a completely disastrous idea.

That said, I'm surprised there is so much of a consensus that Array.Reverse is the fastest method. There's still an unsafe approach that returns a reversed copy of a string (no in-place reversal shenanigans) significantly faster than the Array.Reverse method for small strings:

public static unsafe string Reverse(string text)
{
    int len = text.Length;

    // Why allocate a char[] array on the heap when you won't use it
    // outside of this method? Use the stack.
    char* reversed = stackalloc char[len];

    // Avoid bounds-checking performance penalties.
    fixed (char* str = text)
    {
        int i = 0;
        int j = i + len - 1;
        while (i < len)
        {
            reversed[i++] = str[j--];
        }
    }

    // Need to use this overload for the System.String constructor
    // as providing just the char* pointer could result in garbage
    // at the end of the string (no guarantee of null terminator).
    return new string(reversed, 0, len);
}

Some benchmark results:

1000000 strings, 5 characters each:
 946.8337 ms (Array.Reverse method)
 792.3596 ms (safe variation of above method)
 327.5075 ms (unsafe version posted bove)

1000000 strings, 10 characters each:
1077.9051 ms
1026.4824 ms
 452.2965 ms

1000000 strings, 25 characters each:
1345.3698 ms
1178.9666 ms
 849.9485 ms

500000 strings, 100 characters each:
1089.5289 ms
1516.1195 ms
 924.4814 ms

250000 strings, 200 characters each:
 740.3678 ms
1000.0229 ms
 841.6740 ms

125000 strings, 400 characters each:
 568.6292 ms
 828.5899 ms
 761.3883 ms

You can see that the performance gain shrinks and then disappears against the Array.Reverse method as the strings get larger. For small- to medium-sized strings, though, it's tough to beat this method.

Dan Tao