#python #recursion #dynamic-programming
Вопрос:
Я хотел создать N-мерную доску для тральщиков/Чис, и я столкнулся с проблемой, когда использовал DP для повышения скорости, но скорость, по-видимому, одинакова между двумя версиями.
Версия 1: Наивная рекурсия
def createboard_nd(dimensions, value=None):
if len(dimensions) == 1:
return [value for _ in range(dimensions[0])]
else:
return [createboard_nd(dimensions[1:], value) for _ in range(dimensions[0])]
Версия 2: Рекурсия с DP
def createboard_nd(dimensions, value=None, memo=None):
if memo is None:
memo = {}
if len(dimensions) in memo:
return memo[len(dimensions)]
if len(dimensions) == 1:
memo[len(dimensions)] = [value for _ in range(dimensions[0])]
return memo[len(dimensions)]
else:
memo[len(dimensions)] = [createboard_nd(dimensions[1:],value, memo) for _ in range(dimensions[0])]
return memo[len(dimensions)]
Пример
createboard_nd((10,10,10,10,10,10), 1)
Комментарии:
1. Я обновил пример использования. Это заняло примерно столько же времени
2. Странный. В моем тестировании последнее примерно в 3000 раз быстрее. Какое время вы измеряли для каждого?
3. (Не то, чтобы это действительно имело значение, поскольку оба они делают принципиально разные вещи, и последнее, безусловно, делает не то, что вы хотите.)
4. Не могли бы вы более подробно рассказать о последнем коде?
5. Ну, вы намеренно повторно используете одни и те же объекты списка. Как вы собираетесь поступить с этим позже, когда будете записывать в них данные? Делать копии на лету по мере необходимости? Звучит сложно.
Ответ №1:
Судя по всему, встроенный счетчик времени jupyternotebook имеет ошибку или что-то в этом роде, после запуска версии сценария 2 кажется намного быстрее.