logo标签列表

寻找更高效的算法来打印既是回文数又满足平方也是回文数的数字

c#algorithm
3
我正在寻找更高效的算法，用于打印回文数字（例如1001），以及它们的平方值（1001 * 1001 = 1002001）也是回文数。在我的算法中，我认为我进行了不必要的检查来确定数字是否是回文的。我该如何改进它？
在[1000,9999]范围内，我发现了这3个数字：1001、1111和2002。
以下是我的算法：
for (int i = n; i <= m; i++)
{
    if (checkIfPalindromic(i.ToString()))
    {
        if (checkIfPalindromic((i * i).ToString()))
             Console.WriteLine(i);
    }
}

这是我判断数字是否回文的方法：

static bool checkIfPalindromic(string A)
{
    int n = A.Length - 1;
    int i = 0;
    bool IsPalindromic = true;

    while (i < (n - i))
    {
        if (A[i] != A[n - i])
        {
            IsPalindromic = false;
            break;
        }

        i++;
    }

    return IsPalindromic;
}
一个明显的优化是将 IsPalindromic = false; break 替换为 return false;。一旦确定字符串不是回文，就不需要继续循环了。 - Matthew Watson
好的，谢谢。 - user9790333
看看我的新答案吧！它的速度是原来的两倍。 - Hossein Golshani
@ Hussein Golshani 我会的。 - user9790333
@maxim1000的答案是最好的。不要通过整数迭代，而是通过回文迭代。例如，您将循环遍历所有以12345开头的长度为10的10^5个整数，其中只有一个（以54321结尾的整数）是回文。 - Dave
6个回答
1

您已经拥有的东西似乎相当高效

规模正在检查100万个整数

注意：我使用长整型

免责声明：我必须承认这些结果有点草率，我添加了更多的缩放以便您查看

结果

Mode            : Release
Test Framework  : .Net 4.7.1
Benchmarks runs : 10 times (averaged)

Scale : 1,000
Name     |  Average |  Fastest | StDv |  Cycles | Pass |    Gain
-----------------------------------------------------------------
Mine2    | 0.107 ms | 0.102 ms | 0.01 | 358,770 | Yes  |  5.83 %
Original | 0.114 ms | 0.098 ms | 0.05 | 361,810 | Base |  0.00 %
Mine     | 0.120 ms | 0.100 ms | 0.03 | 399,935 | Yes  | -5.36 %


Scale : 10,000
Name     |  Average |  Fastest | StDv |    Cycles | Pass |    Gain
-------------------------------------------------------------------
Mine2    | 1.042 ms | 0.944 ms | 0.17 | 3,526,050 | Yes  | 11.69 %
Mine     | 1.073 ms | 0.936 ms | 0.19 | 3,633,369 | Yes  |  9.06 %
Original | 1.180 ms | 0.920 ms | 0.29 | 3,964,418 | Base |  0.00 %


Scale : 100,000
Name     |   Average |  Fastest | StDv |     Cycles | Pass |   Gain
--------------------------------------------------------------------
Mine2    | 10.406 ms | 9.502 ms | 0.91 | 35,341,208 | Yes  | 6.59 %
Mine     | 10.479 ms | 9.332 ms | 1.09 | 35,592,718 | Yes  | 5.93 %
Original | 11.140 ms | 9.272 ms | 1.72 | 37,624,494 | Base | 0.00 %


Scale : 1,000,000
Name     |    Average |    Fastest | StDv |      Cycles | Pass |    Gain
-------------------------------------------------------------------------
Original | 106.271 ms | 101.662 ms | 3.61 | 360,996,200 | Base |  0.00 %
Mine     | 107.559 ms | 102.695 ms | 5.35 | 365,525,239 | Yes  | -1.21 %
Mine2    | 108.757 ms | 104.530 ms | 4.81 | 368,939,992 | Yes  | -2.34 %

Mode            : Release
Test Framework  : .Net Core 2.0
Benchmarks runs : 10 times (averaged)

Scale : 1,000,000
Name     |    Average |   Fastest |  StDv |      Cycles | Pass |    Gain
-------------------------------------------------------------------------
Mine2    |  95.054 ms | 87.144 ms |  8.45 | 322,650,489 | Yes  | 10.54 %
Mine     |  95.849 ms | 89.971 ms |  5.38 | 325,315,589 | Yes  |  9.79 %
Original | 106.251 ms | 84.833 ms | 17.97 | 350,106,144 | Base |  0.00 %

Given

protected override List<int> InternalRun()
{
   var results = new List<int>();
   for (var i = 0; i <= Input; i++)
      if (checkIfPalindromic(i) && checkIfPalindromic(i * (long)i))
            results.Add(i);             

   return results;
}

Mine1

private static unsafe bool checkIfPalindromic(long value)
{
   var str = value.ToString();
   fixed (char* pStr = str)
   {
      for (char* p = pStr, p2 = pStr + str.Length - 1; p < p2;)
         if (*p++ != *p2--)
            return false;
   }

   return true;
}

Mine2

private static bool checkIfPalindromic(long value)
{
   var str = value.ToString();
   var n = str.Length - 1;

   for (var i = 0; i < n - i; i++)
      if (str[i] != str[n - i])
         return false;

   return true;
}
1
更乐观的方法是使用int而不是string。这个算法大约快两倍：
static int[] pow10 = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };

static bool checkIfPalindromic(int A)
{
    int n = 1;
    int i = A;
    if (i >= 100000000) { n += 8; i /= 100000000; }
    if (i >= 10000) { n += 4; i /= 10000; }
    if (i >= 100) { n += 2; i /= 100; }
    if (i >= 10) { n++; }


    int num = A / pow10[(n+1) / 2];
    for (; num % 10 == 0;)
        num /= 10;

    int reversedNum = 0;
    for (int input = A % pow10[ n / 2]; input != 0; input /= 10)
        reversedNum = reversedNum * 10 + input % 10;

    return num == reversedNum;
}

使用方法：

for (int i = n; i <= m; i++)
    if (checkIfPalindromic(i) && checkIfPalindromic(i * i))
             Console.WriteLine(i);

基准测试：

Bemchmark in range of [1000, 99999999]  on Core2Duo CPU:

This algorithm: 12261ms
Your algorithm: 24181ms

Palindromic Numbers:
1001
1111
2002
10001
10101
10201
11011
11111
11211
20002
20102
1

不必检查每个数字是否为“回文”，只需迭代遍历回文即可。为此，只需迭代数字的前一半，然后从中组成回文。

for(int half=10;half<=99;++half)
{
    const int candidate=half*100+Reverse(half);//may need modification for odd number of digits
    if(IsPalindrome(candidate*candidate))
        Output(candidate);
}

这将使您的程序的时间复杂度从 O(m) 优化为 O(sqrt(m))，这可能会超过所有常数因子的改进。
0
你可以使用 Linq 来简化你的代码。示例：
static void Main(string[] args)
{
    int n = 1000, m = 9999;
    for (int i = n; i <= m; i++)
    {
       if (CheckIfNoAndPowerPalindromic(i))
       {
           Console.WriteLine(i);
       }
    }
}

private static bool CheckIfNoAndPowerPalindromic(int number)
{
   string numberString = number.ToString();
   string numberSquareString = (number * number).ToString();

   return (Enumerable.SequenceEqual(numberString.ToCharArray(), numberString.ToCharArray().Reverse()) && 
           Enumerable.SequenceEqual(numberSquareString.ToCharArray(), numberSquareString.ToCharArray().Reverse()));
}

output:-
1001
1111 
2002.
@A.M 你是怎么得出那个结论的？能解释一下吗？ - Lucifer
你有没有将其与@matthew建议的优化后进行比较？ - Lucifer
我的时间差 = 0175361微秒 时间差 = 0031125我认为你是正确的 - Lucifer
0

循环到len/2，如下所示：

static bool checkIfPalindromic(string A)
{
    for (int i = 0; i < A.Length / 2; i++)
        if (A[i] != A[A.Length - i - 1])
            return false;

    return true;
}
@A.M 你为什么这样想？ - AustinWBryan
我进行了比较，并发现执行时间上的差异。 - user9790333
0

我们可以通过改变回文检查方法并使用直接整数反转方法来获得有趣的优化，而不是先将数字转换为字符串再在字符串中循环。

我在这个问题的被采纳答案中使用了该方法。

static int reverse(int n)
{
   int left = n;
   int rev = 0;
   int r = 0;
   while (left > 0)
   {
      r = left % 10;
      rev = rev * 10 + r;
      left = left / 10; 
   }
   return rev;
}

我还使用了来自System.Diagnostics的StopWatch来测量经过的时间。

我的检查数字是否为回文数的函数是：

static bool IsPalindromicNumber(int number)
{
   return reverse(number) == number;
}

对于n值为1000，不同的m值得到以下毫秒级别的经过时间结果：

---------------------------------------------------------
| m        | 原始值          | 我的值     | 优化       |
---------------------------------------------------------
|9999      |6.3855           |4.2171      | -33.95%   |
---------------------------------------------------------
|99999     |71.3961          |42.3399     | -40.69%   |
--------------------------------------------------------- 
|999999    |524.4921         |342.8899    | -34.62%   |
---------------------------------------------------------
|9999999   |7016.4050        |4565.4563   | -34.93%   |   
---------------------------------------------------------
|99999999  |71319.658        |49837.5632  | -30.12%   |   
---------------------------------------------------------

测量值是指示性的而不是绝对的，因为从程序的一次运行到另一次运行它们是不同的，但模式保持不变，第二种方法似乎总是更快。

使用StopWatch进行测量：

使用您的方法：

Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();
for (int i = n; i <= m; i++)
{
   if (checkIfPalindromic(i.ToString()))
   {
      if (checkIfPalindromic((i * i).ToString()))
         Console.WriteLine(i);
   }
}
stopWatch.Stop();
Console.WriteLine("First approach: Elapsed time..." + stopWatch.Elapsed + " which is " + stopWatch.Elapsed.TotalMilliseconds + " miliseconds");

我当然使用了完全相同的方法，只不过加入了我的修改：

使用我的方法：

Stopwatch stopWatch2 = new Stopwatch();
stopWatch2.Start();
for (int i = n; i <= m; i++)
{
   if (IsPalindromicNumber(i) && IsPalindromicNumber(i*i))
   {
      Console.WriteLine(i);
   }
}

stopWatch2.Stop();
Console.WriteLine("Second approach: Elapsed time..." + stopWatch2.Elapsed + " which is " + stopWatch2.Elapsed.TotalMilliseconds + " miliseconds");
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接