我正在编写一个快速解决方案，用于解决欧拉问题＃4，其中必须从两个三位数的乘积中找到最大的回文数字。
要确定一个数字是否是回文的，显然需要将该数字的反转与原始数字进行比较。
由于C#没有内置的String.Reverse()方法，那么最快的字符串反转方法是什么？
我将在一个循环中测试所有建议的解决方案，进行10,000,000次迭代。给出最快解决方案的人将获得正确答案。
我将在一个C#.Net 3.5控制台应用程序中测试这个解决方案。
C#.net中字符串反转的最快方法
12
- GateKiller
1
你可能已经过度指定解决方案了，特别是因为你的字符串非常小。为什么不询问一个比较两个整数并在它们是回文时返回true的方法呢？ - jdigital
11个回答
20
颠倒数字会更快吗？
// 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;
}
- configurator
6
1+1，这比将数字转换为字符串、反转它并进行字符串比较要高效得多。 - lacop
您的建议花费了34秒249毫秒。 - GateKiller
@configurator：感谢你的努力 :) 我接受了 P Daddy 的代码，因为它明确回答了原始问题。此外，ggf31416的FastReverse函数速度更快。 - GateKiller
配置器：您的赞数比被采纳的答案还要多。这已经说明了一切。;] - bzlm
请问能否解释一下模10是什么意思？
ulong digit = number % 10; - Florian
1任何数模10的结果都是它的个位数 - 因此
digit始终是number的个位数。 - configurator14
如果您想将一个数字与它的反向数进行比较，使用除法翻转数字可能比将其转换为字符串更快。 我仍需要测试其速度。
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 ;
}
将方法返回布尔值比在循环中与布尔值进行比较稍微慢了一些，但我不明白为什么。请在您的计算机上测试。
乘法和位移操作应该比除法更快，但可能不够精确。编辑：使用 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。
- ggf31416
4
我之前不知道有 Math.DivRem 这个函数。很不错的功能。 - configurator
你的第一个建议花费了36秒816毫秒，而你的第二个建议只花费了34秒74毫秒。 - GateKiller
1哎呀！您的第三个建议花费了13秒916毫秒！ - GateKiller
不错的技巧！对于那些不理解为什么这样做有效的人来说，“>> 31”相当于除以2,147,483,648。因此，乘以214,748,365然后除以2,147,483,648得到的结果与除以10相同（由于整数截断），但速度要快得多，因为除法非常慢。 - P Daddy
12
我认为在原地比较可能会更快。如果你反转字符串，你需要：
- 实例化一个新的字符串对象（或StringBuffer对象）
- 将数据（反转后）从第一个字符串复制到新字符串
- 进行比较。
如果您在原地执行比较，则只需执行最后一步。即使这样，您的比较也仅限于字符串的一半（如果字符数为奇数，则是半数减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;
}
编辑：
虽然这回答了问题，但根据我的测试，ggf31416和configurator提供的解决方案可以比本题作者提供的解决方案更快地解决原问题，快约30％。如果将其转换为静态方法并使用int而不是ulong，则configurator的解决方案略快于ggf31416的解决方案（否则要慢得多）。
顺便说一句，通过以下简单（也许有些天真）的循环运行这些示例来解决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()) 耗时0.3064174秒。 ggf31416Reverse(product) == product 耗时0.1933994秒。 configuratorReverse(product) == product 耗时0.1872061秒。
每个方法都得到了正确的结果913 * 993 = 906609。
- P Daddy
1
您的建议花费了49秒435毫秒。 - GateKiller
3
string test = "ABC";
string reversed = new String(test.ToCharArray().Reverse().ToArray());
- user53791
1
您的建议花费了1分51秒608毫秒。 - GateKiller
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);
}
编辑：哎呀！忘记了为了性能要把长度减半 :)
- JaredPar
1
您的建议花费了1分49秒919毫秒。 - GateKiller
1
我发现在C#中反转字符串的最快方法是使用以下代码。它以每次读取32位而不是16位char的长度更快。
在调试模式下，它比Array.Reverse()更快，直到达到大约93个字符。超过这个长度，Array.Reverse()更快。使用发布版本并在IDE外运行，此方法将在任何字符串长度下击败Array.Reverse()。
char[] MyCharArray = MyString.ToCharArray();
UIntStringReverse(ref MyCharArray); //Code to reverse is below.
string ReversedString = new string(MyCharArray);
private static unsafe void UIntStringReverse(ref char[] arr)
{
uint Temp;
uint Temp2;
fixed (char* arrPtr = &arr[0])
{
uint* p, q;
p = (uint*)(arrPtr);
q = (uint*)(arrPtr + arr.LongLength - 2);
if (arr.LongLength == 2)
{
Temp = *p;
*p = ((Temp & 0xFFFF0000) >> 16) | ((Temp & 0x0000FFFF) << 16);
return;
}
while (p < q)
{
Temp = *p;
Temp2 = *q;
*p = ((Temp2 & 0xFFFF0000) >> 16) | ((Temp2 & 0x0000FFFF) << 16);
*q = ((Temp & 0xFFFF0000) >> 16) | ((Temp & 0x0000FFFF) << 16);
p++;
q--;
}
}
}
- Harry Glinos
0
string Reverse(string s)
{
return new string(s.ToCharArray().Reverse().ToArray());
}
- zowat
1
虽然不是最高效的，但它是最小和最容易编写的。 - Peter Oehlert
0
使用ggf31416的FastReverse函数，这是Euler项目问题＃4的解决方案，在我的计算机上完成时间为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;
}
}
}
- GateKiller
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接