[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. pe04_001.png

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) pe04_002.png

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.

Recommended Posts

Projet Euler 4 Tentative d'accélération
Projet Euler 7
Projet Euler 47
Projet Euler 31
Numba pour accélérer en Python
Projet Euler 38
Projet Euler 17
Projet Euler 8
Projet Euler 23
Projet Euler 22
Projet Euler 19
Projet Euler 50
Projet Euler 42
Projet Euler 32
Projet Euler 35
Projet Euler 36
Projet Euler 46
Projet Euler 48
Projet Euler 6
Projet Euler 44
Projet Euler 39
Projet Euler 40
Projet Euler 49
Projet Euler 29
Comment accélérer les calculs Python
Projet Euler 27
Projet Euler 41
Projet Euler 18
Projet Euler 13
Projet Euler 30
Projet Euler 16
Projet Euler 14
Projet Euler 34
[DRF] Extrait pour accélérer PrimaryKeyRelatedField
Projet Euler 25
Comment accélérer la belle instanciation de soupe
[Projet Euler] problème1
Comment accélérer Scicit-Learn comme Conda Numpy
[Python] Faites de votre mieux pour accélérer SQL Alchemy
Essais et erreurs pour accélérer la génération de cartes thermiques
Essai et erreur pour accélérer les captures d'écran Android
Tous jusqu'à 775/664, 777/666, 755/644, etc.
Projet Euler15 "Chemin du treillis"
Ce que j'ai fait pour accélérer la tâche de recherche de chaînes
J'ai essayé d'accélérer la création vidéo en traitant en parallèle
Tentative d'ajuster automatiquement la vitesse des vidéos accélérées (partie 2)
Mongodb Shortest Introduction (3) J'ai essayé d'accélérer même des millions
Partie 1 Tentative de codage des mathématiques (∈)
Projet Euler Original Method Group 1
Shell pour créer un projet django
Déployer le projet django sur heroku
Qu'est-ce que Project Euler 3 Acceleration?
N'écrivez pas Python si vous voulez l'accélérer avec Python
[Python] Hit Keras depuis TensorFlow et TensorFlow depuis c ++ pour accélérer l'exécution.
Indispensable si vous utilisez Python! Comment utiliser Numpy pour accélérer les calculs!