我正在爲歐拉問題＃4寫一個快速解決方案，其中必須從兩個3位數字的乘積中找到最大的迴文數。在C＃中反向字符串的最快方法.net
要確定一個數字是否是迴文，您顯然會將數字的反轉與原始數據進行比較。
由於C＃沒有內置的String.Reverse（）方法，反轉字符串的最快方法是什麼？
我將在一個循環中測試所有建議的解決方案，包含100,000,000次迭代。提交最快解決方案的人將得到正確答案。
筆者將要測試在C＃.NET 3.5的控制檯應用程序解決方案
我想這可能是快做就地進行比較。如果顛倒的字符串，你得：
如果您在原地進行比較，那麼您只做最後一步。即使如此，你的比較只是字符串的一半（或者一半 - 在奇數字符的情況下爲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和configurator提供的解決方案解決了OP的實際需求約30％的速度，通過我的測試。配置器的解決方案比ggf31416快一點，如果將其轉換爲靜態方法並使用int s而不是ulong s（但要慢得多，否則）。
順便說一下，通過這些實例運行解決與下面的簡單（也許天真）循環的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正確的結果。
您的建議花了49秒435ms – GateKiller 2009-01-11 18:56:16
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);
}
編輯：衛生署！忘記減半長度PERF :)
你的建議花了1分49秒919ms – GateKiller 2009-01-11 18:49:28
string test = "ABC";
string reversed = new String(test.ToCharArray().Reverse().ToArray());
你的建議花了1分51秒608ms – GateKiller 2009-01-11 18:53:43
string Reverse(string s)
{
return new string(s.ToCharArray().Reverse().ToArray());
}
雖然不是最高性能，但它是最小和最容易寫的。 – 2009-01-11 19:06:33
你想比較一個數字與其相反，它可能會更快地反轉使用除法的數字，而不是將其轉換爲字符串。我仍然需要測試它的速度。
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 ;
}
使得該方法返回一個布爾比在我的電腦上一個循環比較的布爾稍微慢一些，但我不明白爲什麼。請在您的電腦上測試。
乘法和位移應該比除法更快，但可能不夠精確。編輯：使用長期似乎是足夠精確。
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，直到1073741829其中，1/10給出107374182和乘法+二進制移位給出107374183.
我對Math.DivRem不瞭解。很好的接觸。 – configurator 2009-01-11 17:31:25
你的第一個建議花了36秒816ms，你的第二個建議花了34秒74ms – GateKiller 2009-01-11 19:01:58
OMG！你的第三個建議花了13秒916ms！ – GateKiller 2009-01-11 19:28:12
豈不反轉數更快？
// 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;
}
使用ggf31416的快退功能，這裏是項目歐拉的問題＃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;
}
}
}
Stopwatch類需要在每次運行後重置。下面的代碼已被校正
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;
}
}
}
我發現扭轉C＃字符串是用下面的代碼的最快方式。它的讀取速度是32位，而不是16位的字符長度。 在調試模式下，速度要快到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--;
}
}
}
您可能已經超出瞭解決方案的範圍，尤其是因爲您的字符串太小。爲什麼不要求一種比較兩個整數的方法，如果它們是迴文的話就返回true？ – jdigital 2009-01-11 17:15:21