如何优化python代码: Euler projec prob 4

Question

我一直在Euler project problem 4上工作，我的代码运行得很好，但它花费了太多的时间(0.41秒).How我可以优化它，使它占用更少的time.Is，有一个我遗漏的技巧，或者是我不知道的特殊函数？

代码如下：

#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                  

Answer 1

既然代码的运行时间小于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已经为false，则A and B不会计算B，因此它知道A and B必须为false。(这称为“短路”；如果A为真，“A或B”也会发生同样的情况。)

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

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

不会改变le。我认为这三行应该等同于le //= 2。

Answer 2

试试这个，它应该不会花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对)。

Answer 3

而不是给你完整的答案。这里有一些指针。

• 重新考虑你的for循环，它们太复杂了。也许内部循环应该从for开始？
• 去掉所有那些愚蠢的if语句，你不需要它们如果i its
• int(str(pot)[::-1])==pot it a

编辑:让男孩/女孩自己解决问题。不需要在这里张贴解决方案。