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,
--
Raul
On Sun, Oct 29, 2017 at 7:38 AM, Erling Hellenäs
<[email protected]> wrote:
> Hi all!
>
> Here Mike Days modification of Esa Lippu algorithm with a fix to generate
> less combinations.
> Faster and uses less memory.
>
>
> 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
>
> )
>
>
> ts'x parELMDE y'
>
> 0.000135765 61440
>
> ts'x parMD y'
>
> 0.000311426 224640
>
>
>
> Cheers,
>
> Erling Hellenäs
>
>
>
>
>
> On 2017-10-29 02:16, Raul Miller wrote:
>>
>> Here's a debugged version of par that seems to have reasonable
>> performance (and good big-O structure):
>>
>> require'stats'
>>
>> par=: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
>> )
>>
>> This could obviously be made a bit more concise,
>>
>> I haven't really been tracking this thread to figure out which are the
>> good performing (and, working properly) variants to test against, if
>> performance is an issue. I have, however, tested it a bit for
>> correctness. Here's the "test suite":
>>
>> NB. borrowed from Lippu Esa
>> nparts=: 4 : 0
>> a=.(y#x) #: i. x^y
>> sort ~.((x=#@~."1 a)#a) </."1 i.y
>> )
>>
>> chk=:2 :0
>> :
>> try.
>> assert x (u -:&(/:~)&:(/:~"1)&:(/:~&.>) v) y
>> catch.
>> echo (":x),' par ',(":y),' NB. failed'
>> throw.
>> end.
>> )
>>
>> check=:par chk nparts
>>
>> 1 check 1
>> 1 check 2
>> 2 check 2
>> 1 check 3
>> 2 check 3
>> 3 check 3
>> 1 check 4
>> 2 check 4
>> 3 check 4
>> 4 check 4
>> 1 check 5
>> 2 check 5
>> 3 check 5
>> 4 check 5
>> 5 check 5
>> 1 check 6
>> 2 check 6
>> 3 check 6
>> 4 check 6
>> 5 check 6
>> 6 check 6
>>
>> 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
