Oops, no... the 1 partition results are not from comb, and 1 comb y won't get them.
I was just using ,.< i.y And, the 2 partition results were also not from comb, I was using ((y#2)#:"1 0 }.i.2^y-1) </."1 i.y Still... tends to be faster than parRuskeyE. Sorry about that, I'm just waking up from a nap... Thanks, -- Raul On Thu, Nov 2, 2017 at 6:29 PM, Raul Miller <[email protected]> wrote: > 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
