generating points on a grid - efficiently

[Rajarshi Guha]

Hi,
I've written some code that takes a N lists of numbers (corresponding to
axes) and generates a list of grid points (N dimensional grid) for the
supplied axes. So as an example say my two axes are defined as

v1 = [1,2,3]
v2 = [1,2,3]

My code will return to me a list of points:

(1,1), (1,2), (1,3) ....(3,1), (3,2), (3,3)

and so on. For 3 axes, I would obtain 27 points and so on.
I've included the code below.

My questions:

Firstly, the code runs in exponential time. Is there any way to
rewrite it to make it more efficient? It seems that this could be
formulated as a recursive problem but I can't seem to get at it.

Secondly, it seems that the repeated use of copy.deepcopy() is very
wasteful? Is there a way I can get around it?

Thanks,

###########################

import copy

def extendgp(g,v):
newg = []
if not g:
for i in v:
newg.append( [i,] )
return newg

for i in g:
for j in v:
x = copy.deepcopy(i)
x.append(j)
newg.append(x)
return newg

def gengrid(axislist):

grid = []
for axes in axislist:
grid = extendgp( grid, axes )
return grid

if __name__ == '__main__':

v1 = [1,2,3]
v2 = [1,2,3]
v3 = [1,2,3]

grid = gengrid( (v1,v2,v3) )
print grid

 

[simon place]

Hi,
I've written some code that takes a N lists of numbers (corresponding to
axes) and generates a list of grid points (N dimensional grid) for the
supplied axes. So as an example say my two axes are defined as

v1 = [1,2,3]
v2 = [1,2,3]

My code will return to me a list of points:

(1,1), (1,2), (1,3) ....(3,1), (3,2), (3,3)

[[a,b] for a in v1 for b in v2]

and so on. For 3 axes, I would obtain 27 points and so on.
I've included the code below.

[[a,b,c] for a in v1 for b in v2 for c in v3]

etc.

then just pick the list comprehension from the count of axes.

or even build the list comp. required in a string and use exec()

My questions:

Firstly, the code runs in exponential time. Is there any way to
rewrite it to make it more efficient? It seems that this could be
formulated as a recursive problem but I can't seem to get at it.

Secondly, it seems that the repeated use of copy.deepcopy() is very
wasteful? Is there a way I can get around it?

Thanks,

alwys be exponential, but list comp. should be fast without much work.

 

[Rajarshi Guha]

Hi,
I've written some code that takes a N lists of numbers (corresponding to
axes) and generates a list of grid points (N dimensional grid) for the
supplied axes. So as an example say my two axes are defined as

v1 = [1,2,3]
v2 = [1,2,3]

My code will return to me a list of points:

(1,1), (1,2), (1,3) ....(3,1), (3,2), (3,3)

[[a,b] for a in v1 for b in v2]

and so on. For 3 axes, I would obtain 27 points and so on.
I've included the code below.

[[a,b,c] for a in v1 for b in v2 for c in v3]

Thanks very much - it speeded it up significantly