I should have special-cased it!!! M Please reply to [email protected]. Sent from my iPad
> On 29 Oct 2017, at 20:12, Erling Hellenäs <[email protected]> wrote: > > At x=:10,y=:10 parELMDE generates !10 combinations. If you only need one it's > quite a lot. Lol. > !10 > > 3.6288e6 > > /Erling > > > > >> On 2017-10-29 20:53, Erling Hellenäs wrote: >> Hi all! >> >> Here y = 12. About the same relation between them as with 10. >> >> y=:12 >> x=:5 >> ts'x parR y' >> 6.88729 7.90934e8 >> ts'x parELMDE y' >> 15.5459 3.62388e9 >> >> Cheers, >> >> Erling Hellenäs >> >>> On 2017-10-29 20:37, Erling Hellenäs wrote: >>> Hi all! >>> >>> I took a sample. We must remember that when we have 10 buckets and 10 >>> elements, we get only one combination. >>> However, it seems Rauls algorithm is better for high y. parELMDE still >>> generates too many unused combinations. >>> >>> x=:5 >>> y=:10 >>> ts'x parR y' >>> 0.211737 2.7077e7 >>> ts'x parELMDE y' >>> 0.417241 1.1325e8 >>> ts'x parMD y' >>> 2.30795 1.71128e9 >>> >>> Cheers, >>> >>> Erling Hellenäs >>> >>>> On 2017-10-29 17:53, Raul Miller wrote: >>>> Ah, excellent. >>>> >>>> require'stats' >>>> >>>> parRDM=:4 :0 >>>> x (1+y-x) P y >>>> ) >>>> >>>> combine=:1 :0 >>>> : >>>> q=.(#;{.x)=#@>y >>>> if.1 e.,q do. >>>> b=. ,(<./@>x)<:/ q <./@;@#"1 y >>>> b # ,/ x ([,] ({L:0 ,) (i.m)-.S:0 [)"0 1/ y >>>> else. >>>> ,/ x ([,] ({L:0 ,) (i.m)-.S:0 [)"0 1/ y >>>> end. >>>> ) >>>> >>>> >>>> P=:1 :0 >>>> : >>>> NB. x: number of partitions >>>> NB. m: maximum allowed partition size >>>> NB. y: number of items to distribute across partitions >>>> if. y>x*m do.return. end. >>>> if. (0=m)+.y<x do.return.end. >>>> if.1=x do. ,.<"1 m comb y return.end. >>>> r=.i.0 0 >>>> for_n. 1+i.m do. >>>> t=.(x-1) (m<.(y-n)<.n) P y-n >>>> if. 0=#t do. continue. end. >>>> c=.<"1 n comb y >>>> r=.r, c y combine t >>>> end.r >>>> ) >>>> >>>> parELMDE=: 4 : 0 >>>> a =. ~. i.~"1 iy #: i. */ iy =. (1+i.x),(y-x)$x >>>> a =. a#~ x = #@~."1 a >>>> sort a </."1 i. y >>>> ) >>>> >>>> timerat=:4 :0"0 >>>> try. >>>> elmde=.6!:2 'vE=. x parELMDE y' >>>> rdm=.6!:2 'vR=. x par y' >>>> r=. rdm%elmde >>>> catch. >>>> vR=.vE=.0 >>>> r=. _ >>>> end. >>>> assert. vR -:&(/:~)&:(/:~"1)&:(/:~&.>) vE >>>> r >>>> ) >>>> >>>> For the simple (and fast) cases, parELMDE tends to be significantly >>>> faster than my parRDM. Low complexity pays off: >>>> >>>> 3 timerat 4 >>>> 2.59375 >>>> >>>> However, for other cases, it tends to be significantly slower. Here, >>>> low complexity does not pay off enough to amortize big-O issues: >>>> >>>> 6 timerat 8 >>>> 0.067733 >>>> >>>> Or, a slightly better overview (better viewed with fixed width font or >>>> run it yourself): >>>> >>>> 9!:11]3 NB. reduce display precision, for email line widths >>>> >>>> (1+i.10) timerat table 1+i.10 >>>> ┌───────┬─────────────────────────────────────────────────────────────┐ >>>> │timerat│ 1 2 3 4 5 6 7 8 9 10│ >>>> ├───────┼─────────────────────────────────────────────────────────────┤ >>>> │ 1 │1.03 1.38 1.67 1.82 2.3 2.5 2.9 3.1 3.4 3.7│ >>>> │ 2 │ _ 5.43 3.28 5.13 3.6 3.95 2.36 2.37 1.52 1.58│ >>>> │ 3 │ _ _ 5.46 3.24 3.24 2.27 1.46 1.43 0.83 0.763│ >>>> │ 4 │ _ _ _ 2.94 1.74 1.44 0.961 0.668 0.599 0.621│ >>>> │ 5 │ _ _ _ _ 2.08 0.514 0.374 0.325 0.315 0.311│ >>>> │ 6 │ _ _ _ _ _ 0.566 0.0929 0.0876 0.0951 0.124│ >>>> │ 7 │ _ _ _ _ _ _ 0.0936 0.0156 0.0177 0.0323│ >>>> │ 8 │ _ _ _ _ _ _ _ 0.0117 0.00192 0.00209│ >>>> │ 9 │ _ _ _ _ _ _ _ _ 0.00256 0.000176│ >>>> │10 │ _ _ _ _ _ _ _ _ _ 0.00019│ >>>> └───────┴─────────────────────────────────────────────────────────────┘ >>>> >>>> Thanks, >>>> >>> >>> ---------------------------------------------------------------------- >>> For information about J forums see http://www.jsoftware.com/forums.htm >> >> >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
