Beschleunigen rekursive Methode durch Umwandlung in iterative

Question

Ich schreibe einen dynamischen Programmieralgorithmus in Python, die perfekt für kleinere Eingaben funktioniert, aber es Timeout für große Eingaben wahrscheinlich wegen der rekursiven Aufrufe. Ich lese diese article online, die besagt, dass die meisten modernen Programmiersprachen nicht mit Rekursion gut umgehen, und es ist eine bessere Idee, sie in eine iterative Methode zu konvertieren.

Mein Algorithmus ist wie folgt:

def get_val(x,y,g,i,xlast,ylast): 
    # checks if array over 
    if(i>(len(x)-1)): 
     return 0 
    # else returns the max of the two values 
    # dist returns the euclidian distance between the two points 
    # the max condition just decides if it's profitable to move to the 
    # next x and y coordinate or if it would be better to skip this particular (x, y) 
    return max(g[i]-dist(x[i],y[i],xlast,ylast) + get_val(x,y,g,i+1,x[i],y[i]),get_val(x,y,g,i+1,xlast,ylast)) 

Ich habe versucht, ihre Leistung zu verbessern, aber ich bin nicht wirklich sicher über die Schritte, die ich nehmen sollte, um sicherzustellen, dass es nicht auf große Eingänge hat eine Zeitüberschreitung .

Answer 1

Schreiben einer dynamischen Programmierung Algorithmus setzt voraus, dass Sie bereits mit den rekursiven Aufrufen zu tun haben, so dass Ihre aktuellen Code ist nicht dynamisch Programmierung noch.

Sie müssen identifizieren, was das Problem verursacht, und dann eine Lösung bereitstellen, die weniger Schritte zum Berechnen der Funktion im Austausch der Speicherbelegung benötigt, dh Speichern von Funktionsaufrufergebnissen, um eine neue Berechnung desselben Aufrufs zu vermeiden.

Ich kenne nicht alle Details Ihres Problems, aber es scheint eine optimal substructure property zu haben.

Sie einen Führer finden, wie Art von Problem zu sagen, was Sie zu tun haben und wie es here

Answer 2

Wenn ich herausfand, was Sie erreichen möchten, könnten Sie einen Generator verwenden, um zum nächsten Schritt zu gehen. Sehen Sie diese Generator Tricks:

http://linuxgazette.net/100/pramode.html

Oder besuchen

https://wiki.python.org/moin/Generators