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
