The performance of your parRuskeyE is looking really nice. That said, for 1 or 2 partitions, a comb based approach (using the comb from require'stats') is still tends to be significantly faster (except for 2 parRuskeyE 2). (And, once the number of values in a partition has reached like 13 or 14, this speed advantage starts creeping into results involving more partitions, but it's not a factor of 2 speed advantage for any practical result size so it's probably not worrying about.)
The 1 partition results would be trivial to incorporate - it's just <"1]1 comb y where y is the number of partitions. Thanks, -- Raul On Thu, Nov 2, 2017 at 9:28 AM, Erling Hellenäs <[email protected]> wrote: > Hi all ! > > My partition projects are parRuskeyE, parE and parE2. > > parRuskeyE > > Frank Ruskeys algorithm, now with massively parallel recursion. > > parE > > Similar to parELMDE, but works with bitmaps and creates less combinations. > > parE2 > > Creates unique bucket groups, combines the buckets within each bucket group > > with sets of combinations with the correct number of items. > > Combinations are filtered to avoid duplication. > > Performance > > ParRuskeyE is the winner in performance with parE not far behind. > > They can all handle high x combined with high y. > > x=:5 > y=:7 > ts'x parRuskeyE y' > 0.000265134 127232 > ts'x parE y' > 0.000889053 794496 > ts'x parE2 y' > 0.00687637 217600 > > x=:5 > y=:10 > ts'x parRuskeyE y' > 0.0683502 3.8954e7 > ts'x parE y' > 0.224765 1.70531e8 > ts'x parE2 y' > 1.50793 6.50278e7 > > x=:9 > y=:10 > ts'x parRuskeyE y' > 0.00013385 75136 > ts'x parE y' > 0.0668154 5.03395e7 > ts'x parE2 y' > 0.0767498 5.86112e6 > > You can see the programs below. > > Cheers, > > Erling Hellenäs > > ---Project--- > > NB. parRuskeyE > > parRuskeyE =: 4 : 0 > r=. (,: i.y) SE (x-1);y-1 > r </."1 i.y > ) > > SE =: 4 : 0 > 'k n' =. y > r=. (0,_1{.$x)$0 > if. k=n do. > r=.x > else. > s=.n {."1 x > e=.(n+1)}."1 x > a=.,/s ( [,"1 1 (i.k+1),"0 1 ])"1 e > r=.r, a SE k;n-1 > if. k > 0 do. > a=.s,.k,.e > r=.r, a SE (k-1);n-1 > end. > end. > r > ) > > NB. parE > > combE=: 4 : 0 > u=:(-y){.i.x-1 > w=:(y#x)-u+|.u > o=:u <@([+[:i.])"0 w > p=:>([:,/[,"0 1 "0 _] )&.>/ (}:o),<,.>{:o > ) > > > parE=: 4 : 0 > NB. Assume a table with x rows and y columns. > NB. Each row is a bucket, each column an item. > NB. Two buckets can not contain the same item. > NB. This means there can only be one item in each column. > NB. Each column can be rotated in x ways. > NB. Generate all combinations of the possible rotations > NB. except for the first and last x-1 columns. > o=: x combE y > NB. Pick the rotation from a bitmap where each > NB. row is a possible rotation > NB. We now have a three-dimensional bitmap of > NB. combination, items in the bucket and bucket > NB. True means the bucket contains the corresponding item > v=:o{(i.x)|."0 1 x{.1 > NB. Select the combination where each bucket contains at least > NB. one item. > b=:(*./"1+./"2 v)#v > NB. Reorder the dimensions > NB. Now they are combination, bucket and items in the bucket. > c=:0 2 1|:b > NB. Sort the buckets within the combinations so that > NB. buckets with the same contents also are in the same place > NB. in bucket order > d=:/:~"2 c > NB. Remove duplicates > e=: ~.d > NB. Display > e<@# i.y > ) > > NB. parE2 > > 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' > > > NB. The argument is a boxed array of combinations > NB. Combine each combination in the last box with all combinations in box > two > NB. from the right. > NB. Continue until all box contents are combined. > 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. > filterMerge=:[: > [: ([: ~.@:(/:~"2)@:; <"2@:] ([ cpE [ filter ])&.> > <@:[)&.>/ ] > > bCombE=: 4 :0 > NB. All combinations of bucket sizes > NB. Which sum to y > v=.1+y-x > p=.>:(x#v)#:i.v^x > r=.(y= +/"1 p)#p > NB. sort them in size order > t=./:~"1 r > NB. Remove duplicates > ~. t > ) > > parE2=: 4 : 0 > NB. All combinations of all items > v=.}.combE2 y > NB.All unique combinations of x buckets with y items > b=.x bCombE y > NB. Unique bucket sizes in all bucket combinations > c=. ~. ,b > NB. Number of items in each combination > d=.+/"1 v > NB. Remove unneded combinations > q=: d e.c > v1=: q#v > d1=: q#d > NB. Insert a bucket dimension. The dimensions are now > NB. bucket combination, bucket and item combination in the bucket > v2=.((#v1),1,y)$,v1 > NB. Pack sets of combinations with number of items corresponding to > NB. the bucket sizes in the classes in c1 > w=.d1</.v2 > c1=. ~.d1 > NB. For all bucket combinations, pack the boxes with the corresponding > NB. number of items and run filterMerge on them > f=. 4 : 'filterMerge x{y' > v32=. ;(<"1 c1 i.b) f&.><w > NB. Select combinations with one and only one of each number > v4=.(1=*/"1 +/"2 v32) # v32 > NB. Pack > v4 <@# i.y > ) > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
