On 9/21/07, Gael Varoquaux <[EMAIL PROTECTED]> wrote:
>
> 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.
Try
def triplet(n) :
out = []
for i in xrange(2,n) :
for j in xrange(1,i) :
for k in xrange(0,j) :
out.append((i,j,k))
return out
It's the first algorithm in Knuth, mentioned in passing.
In [7]: time a = triplet(100)
CPU times: user 0.14 s, sys: 0.01 s, total: 0.14 s
Wall time: 0.15
Which isn't too bad for 161700 combinations. However, I still prefer the
generator form if you want to save memory for large n.
In [2]: def triplet(n) :
...: for i in xrange(2,n) :
...: for j in xrange(1,i) :
...: for k in xrange(1,j) :
...: yield i,j,k
...:
It's a bit slower for making lists, however.
In [24]: time for i,j,k in triplet(100) : a.append((i,j,k))
CPU times: user 0.24 s, sys: 0.01 s, total: 0.25 s
Wall time: 0.25
The more general algorithm L isn't too bad either
In [29]: def combination(n,t) :
....: c = arange(t + 2)
....: c[-1] = 0
....: c[-2] = n
....: while 1 :
....: yield c[:t]
....: j = 0
....: while c[j] + 1 == c[j+1] :
....: c[j] = j
....: j += 1
....: if j >= t :
....: return
....: c[j] += 1
In [30]: for i in combination(5,3) : print i
....:
[0 1 2]
[0 1 3]
[0 2 3]
[1 2 3]
[0 1 4]
[0 2 4]
[1 2 4]
[0 3 4]
[1 3 4]
[2 3 4]
In [31]: time for i in combination(100,3) : pass
CPU times: user 0.58 s, sys: 0.02 s, total: 0.60 s
Wall time: 0.60
Chuck
_______________________________________________
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion
