1

オイラープロジェクトの問題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 秒未満であることが判明したので、それほど興味深いものではなくなりました。コードを変更して、テストする数を減らして、すぐにあきらめることができます。しかし、かわいい最適化が 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

が既に false のA and B場合は B を評価しないため、それが false でなければならないことがわかっています。(これは「ショートサーキット」と呼ばれます。 が true の場合、「A または B」でも同じことが起こります。)AA and BA

ちなみに、ここの最後の行：

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

変わりませんle。これらの 3 つの行は、合計すると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 ペアを 2 回ループしない)。

于 2012-09-03T21:48:13.510 に答える
0

あなたにすべての答えを与えることなく。ここにいくつかのポインタがあります。

  • for ループを再考してください。複雑な方法です。内側のループはi?で開始する必要があります。
  • これらのばかげた if 文をすべて削除します。for ループが正しい場合は必要ありません。
  • 最後にint(str(pot)[::-1])==pot、その回文

編集: 男/女に自分で問題を解決させてください. ここにソリューションを投稿する必要はありません。

于 2012-09-03T21:46:04.560 に答える