Project Euler 4 가속화를 시도했습니다.

요전날 쓴 Project Euler problem 4의 답변 코드를 여러가지 보았다.
ぃ tp // 코 m / 코 f / ms / 1 / 1c2600144520b33f8

문제

左右どちらから読んでも同じ値になる数を回文数という. 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 쪽이 빠르다?
리스트 내포 표기는(쓰는 방법이 나쁜 것일지도 모르지만), 합을 요구하는 등에는 적합하지 않다.

나는 단순한 일요일 프로그래머이며, 전문가가 아니기 때문에 어디까지 맞는지는 수수께끼.