Hi all !
Is this some known algorithm? Ruskey or Knuth, for example.
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
