[PYTHON] Projet Euler 4 Tentative d'accélération

J'ai joué avec le code de réponse pour le problème 4 de Project Euler que j'ai écrit l'autre jour. http://qiita.com/cof/items/1fa1c2600144520b33f8

problème

Le nombre qui a la même valeur lorsqu'il est lu à partir de la gauche ou de la droite est appelé le nombre de fois..Du nombre de fois représenté par le produit de nombres à deux chiffres,Le plus gros est 9009=91 x 99.
Puis,Trouvez le nombre maximum de fois exprimé par le produit de trois chiffres.

Republication du code Instruction while écrite à l'origine (subtilement révisée, comme en faire une fonction) L'impression est commentée car elle a été exécutée 100 fois pour mesurer le temps.

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

À ce stade, j'ai réalisé que je pouvais supposer i> = j, donc je l'ai réécrit en conséquence.

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) #Seulement ici est différent.
    #print max

J'ai essayé d'en faire une déclaration 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

Ici, lors de la mesure du temps d'exécution, while2 était le plus rapide, tandis que1 était le suivant, et for1 était 40% plus élevé que while1, qui était une lente explosion. J'ai deviné que l'appel de la fonction range dans la boucle était la cause du retard, et quand j'ai écrit le code suivant, c'était un peu plus rapide que while1. (Plus lent que 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

J'ai changé cela pour lister la notation d'inclusion.

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

Très simple, mais mortellement lent. La notation d'inclusion de liste est rapide pour créer une liste car elle peut réduire le coût de l'appel de la fonction append (), mais sinon elle semble être très lente si elle est utilisée comme ci-dessus.

De plus, en tant qu'approche différente de ce qui précède, l'approche suivante a été envisagée.

J'ai essayé de mettre ce qui précède dans le code. (Étant donné que ce qui précède est une idée de base, il existe quelques différences dans les détails.)

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

En conséquence, la réponse était aussi grande que 900 000 unités, et le dernier code était le plus rapide. (Exécutez 100 fois)

La conscience d'aujourd'hui: L'utilisation de for in range () dans plusieurs boucles semble augmenter le coût de l'appel de la fonction range. Peut-être que tant est plus rapide que pour? La notation d'inclusion de liste (bien qu'elle puisse être mal écrite) semble ne pas convenir à la recherche de somme.

Je ne suis qu'un programmeur du dimanche, pas un expert, donc c'est un mystère à quel point c'est correct.