在C#.net中反转字符串的最快方法

Question

我正在为Euler Problem#4编写一个快速解决方案,其中必须从两个3位数的乘积中找到最大的回文数.

要确定一个数字是否是回文,您显然会将数字的反转与原始数字进行比较.

由于C#没有内置的String.Reverse()方法,反转字符串的最快方法是什么？

我将在循环中测试所有建议的解决方案,迭代次数为100,000,000次.提交最快解决方案的人将获得正确答案.

我将在C#.Net 3.5控制台应用程序中测试该解决方案

Answer 1

不会更快地扭转这个数字？

// 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 2

你想比较一个数字与它的反向,使用除法转换数字可能会更快,而不是将它转换为字符串.我仍然需要测试它的速度.

 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;
  }

编辑:DivRem比计算机中的分区和模块快1%左右.如果最后一位为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 ;
  }

使方法返回bool比我的计算机中的循环中的bool稍慢,但我不明白为什么.请在您的计算机上测试.

乘法和位移应该比除法快,但可能不够精确.编辑:使用long似乎足够精确.

  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等于i/10,直到1,073,741,829,其中1/10给出107374182,乘法+二进制移位给出107374183.

Answer 3

我认为在原地进行比较可能会更快.如果你反转字符串,你必须:

1. 实例化一个新的字符串对象(或StringBuffer对象)
2. 将数据(反向)从第一个字符串复制到新字符串
3. 做你的比较.

如果您在适当的位置执行比较,则只执行最后一步.即便如此,你的比较只是字符串的一半(或半数 - 0.5,如果是奇数个字符).像下面这样的东西应该工作:

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;
}

编辑:

虽然这解决了OP的问题,但是ggf31416和配置器提供的解决方案通过我的测试解决了OP的实际需求快了约30%.configurator的解决方案比ggf31416快一点,如果你将它转换为静态方法并使用ints代替ulongs(但速度要慢得多).

顺便提一下,通过这些例子来解决问题,OP提到(找到任意两个三位数字的最大回文产品),下面简单(可能是天真的)循环:

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

在我的机器上产生以下结果:

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

每个都产生正确的结果913 * 993 = 906609.