Ускорить рекурсивный метод путем преобразования в итеративный

anonn023432 спросил: 14 ноября 2017 в 05:57 в: python

Я пишу алгоритм динамического программирования в Python, который, кажется, отлично работает для небольших входов, но время ожидания для больших входов истекает, вероятно, из-за рекурсивных вызовов. Я читал эту статью онлайн, в которой говорится, что большинство современных языков программирования плохо справляются с рекурсией, и лучше преобразовать их в итеративный метод.

Мой алгоритм выглядит следующим образом:

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

Я пытался улучшить его производительность, но я не совсем уверен в том, какие шаги я должен предпринять, чтобы не превышать время ожидания при больших входах.

0 ответов