Project Euler 4 高速化を試みた

3738 ワード
ProjectEuler Python Python テキストリンク

先日書いたProject Euler problem 4の回答コードをいろいろいじってみた。
http://qiita.com/cof/items/1fa1c2600144520b33f8

問題

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.

コード再掲
当初書いたwhile文(関数にしたなど、微妙にリバイス済み)
時間計測のため100回実行等をしているため、printをコメントアウトしている。

def while1():
    (i,j)=(999,999)
    max=1

    while i>0:
        while j>0:
            k = i*j
            if k <= max: break
            if str(k)==str(k)[::-1]: max=k
            j -= 1
        (i,j)=(i-1,999)
    #print max

ここで、i>=jと仮定してもよいことに気が付いたので、それに合わせて書き直してみた。

def while2():
    (i,j)=(999,999)
    max=1

    while i>0:
        while j>0:
            k = i*j
            if k <= max: break
            if str(k)==str(k)[::-1]: max=k
            j -= 1
        (i,j)=(i-1,i-1) #ここだけが異なる。
    #print max

for文にしてみた。

def for1():
    start=999
    max=1
    for i in range(start,0,-1):
        for j in range(i,0,-1):
            k = i*j
            if k <= max: break
            if str(k)==str(k)[::-1]: max=k
    #print max

ここで、実行時間を計測してみると、while2が一番早く、while1がその次、for1がwhile1の40%増位など、爆遅であった。
ループの中でrange関数の呼出を行っていることが爆遅となった原因ではないかと推察し、次のコードを書いてみたところ、while1よりも若干早くなったくらいとなった。(while2よりは遅い)

def for2():
    start=999
    max=1
    L = range(start,0,-1)
    for i in L:
        for j in L[start-i:]:
            k = i*j
            if k <= max: break
            if str(k)==str(k)[::-1]: max=k
    #print max

これをリスト内包表記に改めてみた。

def for3():
    L=range(999,0,-1)
    ans = max([i*j for i in L for j in L[999-i:] if str(i*j) == str(i*j)[::-1]])
    #print ans

非常にシンプルだけど、死ぬほど遅い。リスト内包表記はリストを作成するのにはappend()関数の呼出コストを削減できるから早いけど、それ以外で上記のような使い方をするとすごく遅くなりそうである。

また、上記とは別なアプローチとして、以下のようなアプローチを考えてみた。

上記をコードに落とし込んでみた。（上記は基本的アイディアなので、詳細ではいつくか異なる点はある。)

def from999999():
    seed = 999
    max = 999
    min = 99
    ans = 0
    while 1:
        target = seed * 1000 + int(str(seed)[::-1])
        i = max
        while i > min:
            (q, r) =  (target // i, target % i)
            if q > max:
                break
            elif r == 0:
                ans = target
                break
            else:
                i -= 1
        if ans:
            break
        else:
            seed -= 1
    #print ans

結果、答えが90万台と大きいこともあり、最後のコードが最速となった。(100回実行)

今日の気づき：
for in range()を多重ループで使うとrange関数の呼出コストが増えてしまうっぽい。
もしかするとforよりもwhileの方が早い？
リスト内包表記は（書き方が悪いのかもしれないけど）、和を求める等には不向きっぽい。

俺は単なる日曜プログラマであって、専門家ではないのでどこまで正しいかは謎。