反復的な方法を反復的に変換することでスピードアップ

Question

Pythonに動的プログラミングアルゴリズムを書いていますが、小さな入力に対しては完全に機能しているようですが、再帰呼び出しのために大きな入力に対してはタイムアウトします。私はこのarticleをオンラインで読んでいます。これはほとんどの現代のプログラミング言語が再帰をうまく扱いませんし、反復的な方法に変換する方が良い考えです。

次のように私のアルゴリズムは次のとおりです。

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)) 

私はその性能を改善しようとしているが、私は、私はそれが大きな入力にタイムアウトしないことを保証するために必要な手順については本当にわからないんだけど。

Answer 1

をご覧ください。まだプログラミングされていない。

問題の原因を特定してから、メモリ消費と引き換えに関数を計算するための手順が少なくて済む解決策を提供する必要があります。これは関数呼び出しの結果を格納して同じ呼び出しを新たに計算しないようにします。

問題の詳細はわかりませんが、optimal substructure propertyと思われます。

あなたが扱うとどのようにそれをhere

Answer 2

私があなたが達成しようとしているものを見つけたら、ジェネレータを使って次のステップに進むことができます。これらの発電機のトリックを参照してください。

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

それともアルゴリズムはすでに再帰呼び出しを扱っていることを意味するので、あなたの現在のコードが動的ではありませんダイナミックプログラミングを書く

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