[Numpy-discussion] Extracting all the possible combinations of a grid

Gael Varoquaux gael.varoquaux@normalesup....
Fri Sep 21 16:17:17 CDT 2007


On Fri, Sep 21, 2007 at 02:58:43PM -0600, Charles R Harris wrote:
>    I found generators a good approach to this  sort of thing:

>    for (i,j,k) in triplets(n) :

That's what we where doing so far, but in the code itself. The result was
unbearably slow.
I think for our purposes we should build a precalculated table of these
nuplets, and then do array calculations on them.

I was just wondering what the good way to build this table was. And I
immediately thought of using tricks on arrays without realizing the speed
at which the combination diverged.

In the worst case, a set of nested for loops in a weave.inline wrapped C
code populating an array of (n**d/n!, d) size would do the trick and be
real fast. Something like (implemented in C, rather than Python):

index = 0
for i in xrange(n):
    for j in xrange(i):
	for k in xrange(j):
	    index += 1
	    out_array(index, 0) = i
	    out_array(index, 1) = j
	    out_array(index, 2) = k

This would scale pretty well IMHO.

Now if this array does not fit in memory, then we have a problem. It
means we need to generate a set of smaller arrays. Which should not be a
tremendous problem: just extract the outer loop from the code in C, and
produce one by one the arrays (this can be implement with a generator, I
agree). I have already done this trick of grouping operations on arrays
slightly smaller than the max memory on other code and it worked very
well, much better than not using arrays.

Now we need some numbers on the size of the problem to proceed. But it's
Friday night in France, and the kid must be out having fun :->.

Thanks for you advice,

Gaël


More information about the Numpy-discussion mailing list