Yes - even with your improvement, it works by filtering an ever larger array. I’ll post separately a reasonably “constructive” approach, which is closer to Raul’s method in performance, I think. Mike
Please reply to [email protected]. Sent from my iPad > On 29 Oct 2017, at 19:37, Erling Hellenäs <[email protected]> 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
