1

我一直在研究 Euler 项目问题 4，我的代码运行良好，但需要花费太多时间（0.41 秒）。如何优化它以减少时间。是否有我遗漏或特殊的技巧我不知道的功能？
这是代码：

#Note: tpal is a function to test if number is palindrome

pal =0

for i in range(999,100,-1):
    if pal >= i*999:    #A way to get out of loop and to not test on all numbers
        break 
    for j in range(999,100,-1):
        if pal >= i*999:
            break 
        if j > i:                         #numbers would already have been tested so I skip them 
            continue
        pot=i*j
        if ((tpal(pot)==1)and(pot> pal)):
            pal=pot
            i1=i
            j1=j

print(i1,j1,pal)

def tpal(num):
    num=list(str(num))
    Le=len(num)
    if Le == 1: # if number is of one digit than palindrome
        return 1

    le=len(num)

    if le%2 !=0: #4 example 10101even nbr
        le-=1
    le/2    

    for i in range(0,le):
       if num[i]!=num[Le-i-1]:
           return 0

    return 1
4

3 回答 3

2

现在事实证明代码的运行时间 < 1 秒，它不再那么有趣了。您可以修改代码以测试更少的数字并尽早放弃。但是有一个明显的优化有点可爱。这一行：

        if ((tpal(pot)==1)and(pot> pal)):

每次都检查某事物是否是回文，即使pot <= pal. 回文测试很昂贵。如果您只是交换订单：（请注意，您不需要==1）：

        if (pot > pal) and tpal(pot):

那么你可以节省很多时间：

In [24]: timeit orig()
1 loops, best of 3: 201 ms per loop

In [25]: timeit orig_swapped()
10 loops, best of 3: 30.1 ms per loop

因为A and B如果 B 已经为假，则不评估 B A，因此它知道A and B必须为假。（这称为“短路”；如果A为真，“A 或 B”也会发生同样的情况。）

顺便说一句，这里的最后一行：

if le%2 !=0: #4 example 10101even nbr
    le-=1
le/2    
^^^^

没有改变le。我认为这三行的意思是le //= 2。

于 2012-09-03T22:44:08.967 回答
1

试试这个，它不应该花费将近 31 秒：

def isPalindrome(n):
    return str(n) == str(n)[::-1]

def listNums():
    a, b, pal = 0, 0, 0;
    for i in range(999, 99, -1):
        for j in range(999, 99, -1):
            n = i * j
            if isPalindrome(n) and n > pal:  # better to use "n > pal and isPalindrome(n)" instead, see other answer for details.
                a, b, pal = i, j, n
    return a, b, pal             

print listNums()

运行此程序大约需要 1 秒。对于这样的事情，你当然不需要if循环中那些多余的语句——如果你循环，比如说，range(9999, 999, -1)你可能会考虑做一些这样的优化（当然，有很多潜在的优化可以对某些东西进行像这样，例如不循环遍历每个 i,j 对两次）。

于 2012-09-03T21:48:13.510 回答
0

没有给你完整的答案。这里有一些指针。

  • 重新考虑你的 for 循环，它们太复杂了。也许内循环应该从i?
  • 删除所有那些愚蠢的 if 语句，如果你的 for 循环是正确的，你就不需要它们。
  • 最后，int(str(pot)[::-1])==pot然后是回文

编辑：让男孩/女孩自己解​​决问题。无需在此处发布解决方案。

于 2012-09-03T21:46:04.560 回答