Hi all!
I have a new version of my original idea. The hopelessly slow one with
all combinations in all buckets.
It is still very slow compared to the ones we have now, but faster than
parEL, at least for high y.
x=:5
y=:8
ts'x parEL y'
4.74682 1.51822e8
ts'x parE y'
0.974468 6.85389e6
ts'x parELMDE y'
0.00635465 3.28064e6
I might be able to improve it further, but this is how it looks now:
NB. All combinations of y items
combE2=: 3 : 'm{.#:i.m=.(0~:#y)*<.2^y'
NB. Select from y where there are no item duplicates in the buckets of x
NB. and the buckets of y.
filter=: 4 : '(x -.@:(+./)@:*.&(+./)"2 y)#y'
NB. Cartesian product
NB. If y is empty after filter the result will be empty
cpE=: 4 : 'x,"2 y'
parE =: 4 : 0
NB. All combinations of all items
v=.}.combE2 y
NB. Select combinations with less than or equal to 1+y-x items
v1=.((+/"1 v)<:1+y-x)#v
NB. Insert a bucket dimension. The dimensions are now
NB. bucket combination, bucket and item combination in the bucket
v11=.((#v1),1,y)$,v1
NB. Put all combinations in bucket one,
NB. Combine each combination with all combinations in bucket two
NB. Continue until all buckets are filled.
NB. BUT - Filter the incoming combinations before the cartesian product
NB. AND - AFTER the cartesian product -
NB. -Sort the buckets in each bucket combination to get equal bucket
combinations in
NB. the same bucket number.
NB. -Remove duplicates.
v21=.>([: ~.@:(/:~"2)@:; <"2@:] ([ cpE [ filter ])&.> <@:[)&.>/x#<v11
NB. Select combinations with one and only one of each number
v3=.(1=*/"1 +/"2 v21) # v21
NB. Pack
v3 <@# i.y
)
Cheers,
Erling Hellenäs
Den 2017-10-29 kl. 21:12, skrev Erling Hellenäs:
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
