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.