От рекурсивного алгоритма к подходу динамического программирования снизу вверх - PullRequest
Новая
       50

От рекурсивного алгоритма к подходу динамического программирования снизу вверх

0 голосов
/ 06 апреля 2019

У меня есть рекурсивный алгоритм, в котором я вычисляю некоторые значения вероятности.Входные данные представляют собой список целых чисел и одно целочисленное значение, которое представляет собой постоянное значение.

Например, p([12,19,13], 2) делает три рекурсивных вызова, которые

p([12,19],0) и p([13], 2)

p([12,19],1) и p([13], 1)

p([12,19],2) и p([13], 0)

, поскольку 2 можно разложить на 0 + 2, 1 + 1 или 2 + 0,Затем каждый вызов следует подобному подходу и делает несколько других рекурсивных вызовов.

Рекурсивный алгоритм, который у меня есть 

limit = 20
def p(listvals, cval):
    # base case
    if len(listvals) == 0:
        return 0

    if len(listvals) == 1:
        if cval == 0:
            return listvals[0]/limit
        elif listvals[0] + cval > limit:
            return 0
        else:
            return 1/limit

    result = 0
    for c in range(0,cval+1):
        c1 = c
        c2 = cval-c
        listvals1 = listvals[:-1]
        listvals2 = [listvals[-1]]
        if listvals[-1] + c2 <= limit:
            r = p(listvals1, c1) * p(listvals2, c2)
            result = result+r

    return result

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

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

Я попытался создать словарь предварительно вычисленных значений, как показано ниже 

m[single_value]=[list of calculated values]

, и использовать эти значения вместо выполнения второго рекурсивного вызова p(listvals2, c2), но это не помоглоне сильно помогает в отношении времени выполнения.

Как я могу улучшить время выполнения, используя правильный подход снизу вверх?

1 Ответ

1 голос
/ 06 апреля 2019

Не уверен, что я понимаю, что ваша программа хочет вычислить, поэтому не могу помочь с этим, может быть, объясните немного больше?

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

Стандартная библиотека Python functools предоставляет простой способ сделать этот довольно распространенный фрагмент. 

from functools import wraps

def cached(func):
  cache = {}
  @wraps(func)
  def wrapped(listvals, cval):
    key = (listvals, cval)
    if key not in cache:
        cache[key] = func(key)
    return cache[key]
  return wrapped

Используйте этот декоратор для кэширования всех вызовов функции: 

@cached
def p(listvals, cval):

Теперь возьмите p кортеж вместо списка: 

p((12,19,13), 2)
...