Project Euler #4 算法的可能优化

Question

Find the largest palindrome made from the product of two 3-digit numbers.

尽管该算法对于手头的问题足够快，但我想知道我是否遗漏了任何明显的优化。

from __future__ import division
from math import sqrt

def createPalindrome(m):
    m = str(m) + str(m)[::-1]
    return int(m)

def problem4():
    for x in xrange(999,99,-1):
        a = createPalindrome(x)
        for i in xrange(999,int(sqrt(a)),-1):
            j = a/i
            if (j < 1000) and (j % 1 == 0):
                c = int(i * j)
                return c

Answer 1

寻找 here 的想法

在 C++ 中我是这样做的：

int euler004()
    {
    // A palindromic number reads the same both ways. The largest palindrome
    // made from the product of two 2-digit numbers is 9009 = 91  99.
    // Find the largest palindrome made from the product of two 3-digit numbers.
    const int N=3;
    const int N2=N<<1;
    int min,max,a,b,c,i,j,s[N2],aa=0,bb=0,cc=0;
    for (min=1,a=1;a<N;a++) min*=10; max=(min*10)-1;
    i=-1;
    for (a=max;a>=min;a--)
     for (b=a;b>=min;b--)
        {
        c=a*b; if (c<cc) continue;
        for (j=c,i=0;i<N2;i++) { s[i]=j%10; j/=10; }
        for (i=0,j=N2-1;i<j;i++,j--)
         if (s[i]!=s[j]) { i=-1; break; }
        if (i>=0) { aa=a; bb=b; cc=c; }
        }
    return cc; // cc is the output
    }

不需要 sqrt ...
由于 heap/stack 垃圾

createPalindrome

字符串操作 m = str(m) + str(m)[::-1] 很慢
如果您自己在固定大小的数组上进行字符串到 int 的转换会更快
我的实现运行大约 1.7 毫秒，但大部分时间是应用程序输出和格式化（W7 x64 上的 AMD 3.2GHz 32 位应用程序）...

[edit1] 实施您的公式

int euler004()
    {
    int i,c,cc,c0,a,b;
    for (cc=0,i=999,c0=1100*i;i>=100;i--,c0-=1100)
        {
        c=c0-(990*int(i/10))-(99*int(i/100));
        for(a=999;a>=300;a--)
         if (c%a==0)
            {
            b=c/a;
            if ((b>=100)&&(b<1000)) { cc=c; i=0; break; }
            }
        }
    return cc;
    }

这需要大约 0.4 毫秒

[edit2] 进一步优化

//---------------------------------------------------------------------------
int euler004()
    {
    // A palindromic number reads the same both ways. The largest palindrome
    // made from the product of two 2-digit numbers is 9009 = 91  99.
    // Find the largest palindrome made from the product of two 3-digit numbers.
    int i0,i1,i2,c0,c1,c,cc=0,a,b,da;
    for (c0=  900009,i0=9;i0>=1;i0--,c0-=100001)    // first digit must be non zero so <1,9>
    for (c1=c0+90090,i1=9;i1>=0;i1--,c1-= 10010)    // all the rest <0,9>
    for (c =c1+ 9900,i2=9;i2>=0;i2--,c -=  1100)    // c is palindrome from 999999 to 100001
     for(a=999;a>=948;a-- )
      if (c%a==0)
        {
        // biggest palindrome is starting with 9
        // so smallest valid result is 900009
        // it is odd and sqrt(900009)=948 so test in range <948,999>
        b=c/a;
        if ((b>=100)&&(b<1000)) { cc=c; i0=0; i1=0; i2=0; break; }
        }
    return cc;
    }
//---------------------------------------------------------------------------

这太快了，我无法正确测量时间（原始时间约为 0.037 毫秒）
从回文生成中删除了除法和乘法
在等待公交车时进行一些数值分析和思考后更改了范围
可以消除第一个循环（结果以9开头）

Answer 2

我刚开始学习的时候写过这个python，但是这里是：

for i in range (999, 800, -1):

for j in range (999,800, -1):

    number = i*j
    str_number = str(number)

rev_str_number = str_number[::-1]

if str_number == rev_str_number:

    print("%s a palendrome") % number

我没有检查你做的所有数字，但我仍然得到了正确答案。我在这个练习中真正学到的是“::”及其工作原理。您可以查看 here.

祝欧拉好运！

Answer 3

我的代码中最大的减速似乎是将整数转换为字符串，加上它的反向并将结果转换回整数。

我查找了更多关于回文的信息，偶然发现了这个公式，它允许我将 3 位数字 "n" 转换为 6 位回文 "p"（可以适用于其他数字，但我并不担心）。

p = 1100*n−990*⌊n/10⌋−99*⌊n/100⌋

我的原始代码运行时间约为 0.75 毫秒，而新代码的运行时间几乎相同（更不用说公式必须根据 "n" 的位数进行调整），所以我想没有多少优化可以执行了。

Project Euler #4 算法的可能优化

Possible optimizations for Project Euler #4 algorithm

python

math

palindrome