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
