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

我写这篇文章是在我刚开始学习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

我没有核对你所有的数字，但我还是得到了正确的答案。我在这个练习中真正学到的是“：”以及它是如何工作的。{a1}你可以看看。在

祝欧拉好运！在

Answer 2

找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。。。在
• 对createPalindrome的子调用会由于堆/堆栈垃圾而减慢速度
• 字符串操作m = str(m) + str(m)[::-1]很慢
• 如果您自己在固定大小的数组上执行字符串到int的转换，则可以更快
• mine的实现大约运行1.7毫秒，但大部分时间是应用程序输出和格式化（AMD 3.2GHz 32位应用程序W7x64）。。。在

[edit1]实现公式

^{pr2}$

• 这需要~0.4毫秒

[edit2]进一步优化

^{3}$

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

Answer 3

在我的代码中，似乎最大的减速是将一个整数转换成一个字符串，再加上它的逆数，然后将结果转换回整数。在

我查阅了更多关于回文的信息，偶然发现了这个公式，这个公式允许我将3位数的数字“n”转换成6位数的回文“p”（可以适用于其他数字，但我不关心这个问题）。在

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

我的原始代码大约在0.75毫秒内运行，而新代码所用的时间几乎相同（更不用说公式必须根据“n”的位数进行调整），所以我想剩下的优化不多了。在