Quickest Method to Reverse in String in C#.net

Question

Thank you for your entries. Here is my response.

I'm currently writing a quick solution for Euler Problem #4 where one must find the largest palindromic number from the product of two 3-digit numbers.

To identify if a number is palindromic, you would obviously compare a reverse of the number with the original.

Since C# doesn't have a built in String.Reverse() method, what is the quickest way to reverse a string?

I will be testing all the suggested solution in a loop with 100,000,000 itterations. The correct answer will be given to the person who submitted the fastest solution.

I will be testing the solution in a C#.Net 3.5 console application

Answer 1

public static String Reverse(string input) {
  var length = input.Length;
  var buffer = new char[length];
  for ( var i= 0; i < input.Length; i++ ) {
    buffer[i] = input[(length-i)-1];
  }
  return new String(buffer);
}

EDIT: Doh! Forgot to halve the length for perf :)

Answer 2

Performance: Fastest string reversing algorithms... (final results)

Answer 3

try this too: http://weblogs.sqlteam.com/mladenp/archive/2006/03/19/9350.aspx

Answer 4

string test = "ABC";
string reversed = new String(test.ToCharArray().Reverse().ToArray());

Answer 5

string Reverse(string s)
{
  return new string(s.ToCharArray().Reverse().ToArray());
}

Answer 6

I think it might be faster to do the comparison in-place. If you reverse the string, you've got to:

1. Instantiate a new string object (or StringBuffer object)
2. Copy the data (in reverse) from the first string to the new string
3. Do your comparison.

If you perform the comparison in place, you do only the last step. An even then, your comparison is only half the string (or half - 0.5, in the event of an odd number of characters). Something like the following should work:

static bool IsPalindromic(string s){
    int len = s.Length;
    int half = len-- >> 1;
    for(int i = 0; i < half; i++)
        if(s[i] != s[len - i])
            return false;
    return true;
}

EDIT:

Although this answers the OP's question, the solutions offered by ggf31416 and configurator solve the OP's real need about 30% faster, by my tests. configurator's solution is a tiny bit faster than ggf31416's, if you convert it to a static method and use ints instead of ulongs (but much slower, otherwise).

---

Incidentally, running through these examples to solve the problem the OP mentions (finding the largest palindromic product of any two three-digit numbers) with the simple (perhaps naïve) loop below:

for(int i = 100; i < 1000; i++)
    for(int j = i; j < 1000; j++) // calculations where j < i would be redundant
        ...

yields the following results on my machine:

IsPalindromic(product.ToString()) took 0.3064174 seconds.
ggf31416Reverse(product) == product took 0.1933994 seconds.
configuratorReverse(product) == product took 0.1872061 seconds.

Each produces the correct result of 913 * 993 = 906609.

Answer 7

A you want to compare a number with its reverse it may be faster to reverse the number using division rather than converting it to a string. I still need to test the speed of it.

 private static int Reverse(int num) {
     int res = 0;
     while (num > 0) {
        int rm ;
        num = Math.DivRem(num, 10, out rm);
        res = res * 10 + rm;
     }
     return res;
  }

EDIT: DivRem was about 1% faster than division and module in my computer. A speed optimization is exit if the last digit is 0:

  private static int Reverse(int num) {
     int res = 0;
     int rm;
     num = Math.DivRem(num, 10, out rm);
     //Some magic value or return false, see below.
     if (rm == 0) return -1 ; 
     res = res * 10 + rm;
     while (num > 0) {
        num = Math.DivRem(num, 10, out rm);
        res = res * 10 + rm;
     }
     return res ;
  }

Making the method return a bool was slightly slower than comparing to a bool in a loop in my computer, but I don't understand why. Please test in your computer.

Multiplication and bit-shifing should be faster than division but probably are not precise enough. EDIT: using long seems be precise enough.

  private static int FastReverse(int num) {
     int res = 0;
     int q = (int)((214748365L * num) >> 31);
     int rm = num - 10 * q;
     num = q;
     if (rm == 0) return -1;
     res = res * 10 + rm;
     while (num > 0) {
        q = (int)((214748365L * num) >> 31);
        rm = num - 10 * q;
        num = q;
        res = res * 10 + rm;
     }
     return res;
  }

(214748365L * num) >> 31 is equal to i / 10 until 1,073,741,829 where 1 / 10 gives 107374182 and the multiplication + binary shifting gives 107374183.

Answer 8

Wouldn't reversing the number be faster?

// unchecked code, don't kill me if it doesn't even compile.
ulong Reverse(ulong number) {
    ulong result = 0;

    while (number > 0) {
        ulong digit = number % 10;
        result = result * 10 + digit;
        number /= 10;
    }

    return result;
}

Answer 9

Thank you very much for your responses.

I have accepted P Daddy's answer as the correct one because it was the fastest that answered the original questions. Thank P Daddy!

I'd also like to thank ggf31416 & configurator for reading between the lines and comming up mathematical solutions which both took around 34 seconds to do 100 million iterations.

Thanks again :)

Answer 10

Using ggf31416's FastReverse function, here is the solution to Project Euler's Problem #4 which completes on my computer in 47ms.

using System;
using System.Diagnostics;

namespace Euler_Problem_4
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch s = new Stopwatch();
            s.Start();

            int t = 0;

            for (int i = 999; i > 99; i--)
            {
                for (int j = i; j > 99; j--)
                {
                    if (i*j == FastReverse(i*j))
                    {
                        if (i * j > t)
                        {
                            t = i * j;
                        }
                    }
                }
            }

            Console.WriteLine(t);

            s.Stop();
            Console.WriteLine("{0}mins {1}secs {2}ms", s.Elapsed.Minutes, s.Elapsed.Seconds, s.Elapsed.Milliseconds);
            Console.ReadKey(true);

        }

        private static int FastReverse(int num)
        {
            int res = 0;
            int q = (int)((214748365L * num) >> 31);
            int rm = num - 10 * q;
            num = q;
            if (rm == 0) return -1;
            res = res * 10 + rm;
            while (num > 0)
            {
                q = (int)((214748365L * num) >> 31);
                rm = num - 10 * q;
                num = q;
                res = res * 10 + rm;
            }
            return res;
        }
    }
}

Answer 11

The Stopwatch class needs reset after each run. the code below has been corrected

var d = s.ToCharArray();
Array.Reverse(d);
return s == new string(d);

---

using System;
using System.Diagnostics;

namespace longeststring_codegolf
{
    class Program
    {
        static void Main(string[] args)
        {
            int t = 0, v = 0;
            var sw = new Stopwatch();

            sw.Start();
            for (int i = 999; i > 99; i--)
                for (int j = 999; j > 99; j--)
                    if ((v = i * j) > t && IsPalindromicMine(v.ToString()))
                        t = v;
            sw.Stop();

            var elapsed = sw.Elapsed;
            var elapsedMilliseconds = sw.ElapsedMilliseconds;
            var elapsedTicks = sw.ElapsedTicks; 
            Console.WriteLine("Ticks: " + elapsedTicks.ToString());//~189000
            Console.WriteLine("Milliseconds: " + elapsedMilliseconds.ToString()); //~9

            sw = Stopwatch.StartNew();
            for (int i = 999; i > 99; i--)
                for (int j = 999; j > 99; j--)
                    if ((v = i * j) > t && IsPalindromic(v.ToString()))
                        t = v;
            sw.Stop();
            var elapsed2 = sw.Elapsed;
            var elapsedMilliseconds2 = sw.ElapsedMilliseconds;
            var elapsedTicks2 = sw.ElapsedTicks; 
            Console.WriteLine("Ticks: " + elapsedTicks2.ToString());//~388000
            Console.WriteLine("Milliseconds: " + elapsedMilliseconds2.ToString());//~20

        }

        static bool IsPalindromicMine(string s)
        {
            var d = s.ToCharArray();
            Array.Reverse(d);
            return s == new string(d);
        }

        static bool IsPalindromic(string s)
        {
            int len = s.Length;
            int half = len-- >> 1;
            for (int i = 0; i < half; i++)
                if (s[i] != s[len - i])
                    return false;
            return true;
        }

    }
}