Home > Software design >  Python - Dynamic programing doesn't improve speed
Python - Dynamic programing doesn't improve speed

Time:09-17

I wanted to creating N-Dimensional board for Minesweepers/Cheess, and I ran into a problem when I've used DP to improve the speed but, the speed appearingly the same between two version.

Version 1: Naive recursion

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

Version 2: Recursion with 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)]

Example

createboard_nd((10,10,10,10,10,10), 1)

CodePudding user response:

Appearingly jupyternotebook built-in time count has bug or something, after ran script version 2 seem vastly faster.

  • Related