RE: Re: A friendly challenge: Generalized Partition

*To*: mathgroup at smc.vnet.net*Subject*: [mg34945] RE: [mg34932] Re: A friendly challenge: Generalized Partition*From*: "DrBob" <majort at cox-internet.com>*Date*: Fri, 14 Jun 2002 02:38:49 -0400 (EDT)*Reply-to*: <drbob at bigfoot.com>*Sender*: owner-wri-mathgroup at wolfram.com

Lacking sufficient skill to best the methods submitted by Carl, Wolf, Paul, and Andrzej, I merely timed them! I also checked whether they agreed with the original function gg. I called Mr. Wizard's three functions "fast", "short" and "dynamicPartition". Of Hartmut's functions, gg9b gave error messages, so I omitted it from the trials. (It was also SLOW, perhaps because it was busy generating errors.) His first function, which he called gg, I named ggg to avoid confusion. I allowed 0 in b, to make the test slightly more complete, but otherwise used the original test. Andrzej's "cheat" that remembers the answer to avoid recalculating it was called "aa". Here are results sorted by execution time. Where you see False, it means the function got an answer that didn't agree with the original gg. {{aa, True, 0.}, {hh, True, 0.062}, {kk, True, 0.062}, {fast, True, 0.063}, {gg3, True, 0.078}, {dynamicPartition, True, 0.078}, {gg1, True, 0.094}, {gg5, True, 0.125}, {gg2, True, 0.14}, {short, True, 0.188}, {gg4, True, 0.203}, {gg0, True, 0.297}, {ggg, True, 1.391}, {gg11, False, 1.407}, {gg11x, False, 1.438}, {gg, True, 1.547}, {gg7a, False, 1.578}, {gg8c, True, 1.985}, {gg7c, False, 2.047}, {gg8e, True, 2.922}, {gg6, True, 10.047}, {gg10, False, 29.61}} As I suspected, it doesn't seem worthwhile to search farther than Carl's and Andrzej's initial solutions. Next I eliminated aa and all functions with times above 1 second or wrong answers in the list above, and ran a larger test, with 10000 elements in a and 750 in b, and with 200 iterations rather than 100. The times came out fairly interesting (in the same order as above): {{hh, 0.703}, {kk, 0.719}, {fast, 0.718}, {gg3, 0.657}, {dynamicPartition, 0.703}, {gg1, 0.828}, {gg5, 16.765}, {gg2, 1.547}, {short, 1.875}, {gg4, 1.875}, {gg0, 6.61}} gg5 and gg0 come off looking worse, while gg3 looks better than before. Again eliminating those with times over one second, I ran the test again with 20000 elements in a, 1500 in b, and 300 iterations. (I'm a glutton for punishment!) {{fast, 2.375}, {gg3, 2.109}, {dynamicPartition, 2.5}, {kk, 2.485}, {hh, 2.5}, {gg1, 2.547}} For large arrays, I'm going to bet on gg3, but all these algorithms seem to be of the same order. I know this doesn't take the place of a proper complexity analysis of the algorithms, by the way; I'm just having fun, here. Maybe someone can explain WHY gg3 is superior to the others. Bobby Treat -----Original Message----- From: "Mr. Wizard" [mailto:gleam at flashmail.com] To: mathgroup at smc.vnet.net Subject: [mg34945] [mg34932] Re: A friendly challenge: Generalized Partition Since it seems you're all coming up with code pretty much identical to mine, as well as to each other's, I see no point in waiting to post the code I had previously arrived at. My fastest was: f[l_,p_]:=Take[l,#]&/@c@p c=Compile[{{p,_Integer,1}},Transpose@{#~Drop~-1+1,Rest@#}&@FoldList[Plus ,0,p]]; And and shortest: f[l_,p_]:=Block[{v=0},l~Take~{v+1,v+=#}&/@p] I compiled the larger part of the first function shortly before posing this challenge, but doesn't seem to have provided any real advantage, so I am going back a version without it for my own use. I was using length and sum checking to replicate some of the functionality of ggCheckArgs, in this final form: dynamicPartition[l_List,p_List]/;Length@l>=Tr@p:= Take[l,#]&/@Transpose@{#~Drop~-1+1,Rest@#}&@FoldList[Plus,0,p] a more secure check, as (roughly) suggested by Hartmut Wolf, would be: dynamicPartition[l_List,p:{_Integer?NonNegative..}]/;Length@l>=Tr@p:= Take[l,#]&/@Transpose@{#~Drop~-1+1,Rest@#}&@FoldList[Plus,0,p] Paul