[PYTHON] Project Euler 4 Versuch zu beschleunigen

Ich habe mit dem Antwortcode für Project Euler Problem 4 herumgespielt, den ich neulich geschrieben habe. http://qiita.com/cof/items/1fa1c2600144520b33f8

Problem

Die Zahl, die beim Lesen von links oder rechts den gleichen Wert hat, wird als Häufigkeit bezeichnet..Von der Häufigkeit, mit der das Produkt zweistellige Zahlen darstellt,Der größte ist 9009=91 x 99.
Dann,Finden Sie die maximale Anzahl, die durch das dreistellige Produkt ausgedrückt wird.

Code-Repost Ursprünglich geschrieben, während Anweisung (subtil überarbeitet, wie es eine Funktion machen) Der Druck wird auskommentiert, da er 100 Mal ausgeführt wurde, um die Zeit zu messen.

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

Zu diesem Zeitpunkt wurde mir klar, dass ich i> = j annehmen konnte, also schrieb ich es entsprechend um.

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) #Nur hier ist anders.
    #print max

Ich habe versucht, es zu einer for-Aussage zu machen.

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

Bei der Messung der Ausführungszeit war while2 die schnellste, while1 die nächste und for1 40% höher als while1, was eine langsame Explosion war. Ich vermutete, dass das Aufrufen der Bereichsfunktion in der Schleife die Ursache für die Verzögerung war, und als ich den folgenden Code schrieb, war er etwas schneller als while1. (Langsamer als 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

Ich habe dies geändert, um die Einschlussnotation aufzulisten.

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

Sehr einfach, aber tödlich langsam. Die Notation zur Aufnahme von Listen ist schnell zum Erstellen einer Liste, da sie die Kosten für den Aufruf der Funktion append () senken kann. Andernfalls scheint sie bei Verwendung wie oben sehr langsam zu sein.

Zusätzlich wurde als ein Ansatz, der sich von dem oben genannten unterscheidet, der folgende Ansatz in Betracht gezogen.

Ich habe versucht, das oben genannte in den Code einzufügen. (Da dies eine Grundidee ist, gibt es einige Unterschiede in den Details.)

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

Infolgedessen war die Antwort so groß wie 900.000 Einheiten, und der letzte Code war der schnellste. (100 Mal ausführen)

Das heutige Bewusstsein: Die Verwendung von for in range () in mehreren Schleifen scheint die Kosten für den Aufruf der Bereichsfunktion zu erhöhen. Vielleicht ist dabei schneller als für? Die Notation der Listeneinbeziehung (obwohl sie möglicherweise schlecht geschrieben ist) scheint für die Suche nach einer Summe ungeeignet zu sein.

Ich bin nur ein Sonntagsprogrammierer, kein Experte, daher ist es ein Rätsel, wie richtig es ist.