Wednesday, October 22, 2008

String Reverse in C#

 I had to write a string reverse function today and wasn't happy with my initial (basic) function so I posted it on Stack Overflow to see what other algorithms that developers might come up with. My restriction was that it had to be in C# 2.0 and so I couldn't use LINQ. Out of curiosity I decided to do a performance test on each of the functions and while I was at it I threw in the LINQ equivalent to see how it would perform. For the test of a 500 character string I looped each function 100,000 times and for the test of a 10 character string I looped the functions 10,000,000 times.
These are the functions that I tested:
// string concatenation with for loop
public string ReverseA(string text)
{
    char[] cArray = text.ToCharArray();
    string reverse = String.Empty;
    for (int i = cArray.Length - 1; i > -1; i--)
    {
        reverse += cArray[i];
    }
    return reverse;
}

// Array.Reverse function
public string ReverseB(string text)
{
    char[] charArray = text.ToCharArray();
    Array.Reverse(charArray);
    return new string(charArray);
}

// push/pop Stack<>
public string ReverseC(string text)
{
    Stack resultStack = new Stack();
    foreach (char c in text)
    {
        resultStack.Push(c);
    }

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

// LINQ
public string ReverseD(string text)
{
    return new string(text.ToCharArray().Reverse().ToArray());
}

// StringBuilder
public string ReverseE(string text)
{
    char[] cArray = text.ToCharArray();
    StringBuilder reverse = new StringBuilder();
    for (int i = cArray.Length - 1; i > -1; i--)
    {
        reverse.Append(cArray[i]);
    }
    return reverse.ToString();
}


 


What surprised me was how poorley LINQ did on the short string compared to the others.
You may also find the rudimentary test harness that I put together interesting:
delegate string ReverseDelegate(string text);

public void RunPerformance()
{
    int loopCount = 10000000;
    int stringSize = 100;
    string[] reverseTextArray = Enumerable.Repeat("abcde", stringSize).ToArray();
    string reverseText = String.Join("", reverseTextArray);
    // reverseText = "1234567890";
    DateTime startTime, endTime;
   
    ReverseDelegate[] reverseFunc = new ReverseDelegate[5];
    reverseFunc[0] = ReverseA;
    reverseFunc[1] = ReverseB;
    reverseFunc[2] = ReverseC;
    reverseFunc[3] = ReverseD;
    reverseFunc[4] = ReverseE;

    AssertThatFunctionsWorkCorrectly(reverseFunc);

    TimeSpan[] reverseTime = new TimeSpan[reverseFunc.Length];

    for (int i = 0; i < reverseFunc.Length; i++)
    {
        startTime = DateTime.Now;
        for (int j = 0; j < loopCount; j++)
        {
            reverseFunc[i](reverseText);
        }
        endTime = DateTime.Now;
        reverseTime[i] = endTime - startTime;
        Console.WriteLine("{0}/{2} took {1}", i, reverseTime[i], reverseFunc[i].Method);
    }

    Console.WriteLine("break point");
}

private void AssertThatFunctionsWorkCorrectly(ReverseDelegate[] reverseFunc)
{
    string test = "abcdefghi";
    string expected = "ihgfedcba";
    for(int i=0; i

8 comments:

  1. I just posted a follow-up (to your blog and StackOverflow question) with a method that handles Unicode data correctly: code.logos.com/.../how_to_reverse_

    ReplyDelete
  2. char[] charArray = ("Reverse this string.").ToCharArray();
    var stop = Math.Floor((decimal)(charArray.Length / 2));
    int j = 0;
    char tmp;
    for (int i = charArray.Length - 1; i > stop; i--)
    {
    tmp = charArray[j];
    charArray[j] = charArray[i];
    charArray[i] = tmp;
    j++;
    }

    ReplyDelete
  3. @anonymous on 7 Feb: I believe that's what the Array.Reverse(charArray); function does internally.

    ReplyDelete
  4. static void Main(string[] args)
    {
    string item = "the string";
    //assuming string length is > 0 :-).
    int insertPosition = 0;
    char[] chars = new char[item.Length];
    for (int i = item.Length - 1; i >= 0; i--)
    {
    chars[insertPosition] = item[i];
    insertPosition++;
    }
    item = new string(chars);
    Console.WriteLine(item);
    Console.ReadKey();
    }

    ReplyDelete
  5. static void Main(string[] args)
    {
    string item = "the string";
    //assuming string length is > 0 :-).
    int insertPosition = 0;
    char[] chars = new char[item.Length];
    for (int i = item.Length - 1; i >= 0; i--)
    {
    chars[insertPosition] = item[i];
    insertPosition++;
    }
    item = new string(chars);
    Console.WriteLine(item);
    Console.ReadKey();
    }

    ReplyDelete
  6. A friend just made comments (different org via email) to me regarding the LINQ performance, and it prompted me to come back a review more carefully; more specifically, to see how you had used LINQ with this problem.
    So 'politely', I'd say that the extension method used in your example is not LINQ. It's an extension of IEnumerable. LINQ does not really lend itself to this problem (I think).
    While I'd expect an 'array' specific extension method to be fast at reversing an array; I would expect it to grab a memory block and populate by reverse index traversal of the original array.
    However, the Reverse method used is an extension of IEnumerable. Therefore, it has no knowledge of the length of items and will need to fully traverse the items before it can reverse them.
    All that said, and while I recognise that you have to first create the array in your example/ approach, I also note that you have a superfluous statement i.e ToArray.
    return new string(text.ToCharArray().Reverse().ToArray());
    becomes -
    return new string(text.ToCharArray().Reverse());
    What I'd guess IEnumerbale<T>.Reverse() looks like (I have not decompiled this).
    // Sorry, I'm using notepad on a non dev machine and this may have minor errors.
    public static class Extensions
    {
    public static IEnumerable<T> Reverse<T>(IEnumerable<T> this item)
    {
    T[] itemsArray = item.ToArray();
    T[] targetArrary = new T[itemsArray.Length];
    // as per other examples i.e. reverse for
    return targetArray;
    }
    }

    ReplyDelete
  7. Dragged in :-( (now I'm paying for it :-)).
    "The most common extension methods are the LINQ standard query operators ........ "
    Extension methods: msdn.microsoft.com/.../bb383977.aspx
    MSDN wins.

    ReplyDelete