RE: Re: A friendly challenge: Generalized Partition

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

Just to compare results for all three functions on one machine, I tested gg (from the Take documentation), hh (from Carl Woll), and kk (from Andrzej Kozlowski) as follows: Clear[a, b] a = Range[2000]; b = Table[Random[Integer, {1, 20}], {150}]; First[Timing[Do[gg[a, b], {100}]]] First[Timing[Do[hh[a, b], {100}]]] First[Timing[Do[kk[a, b], {100}]]] gg[a, b] == hh[a, b] gg[a, b] == kk[a, b] 0.954 Second 0.062 Second 0.063 Second True True Here's a test ten times larger: a = Range[20000]; b = Table[Random[Integer, {1, 20}], {1500}]; First[Timing[Do[gg[a, b], {100}]]] First[Timing[Do[hh[a, b], {100}]]] First[Timing[Do[kk[a, b], {100}]]] gg[a, b] == hh[a, b] gg[a, b] == kk[a, b] 75.406 Second 0.641 Second 0.625 Second True True worth the search. Notice that hh and kk seem to have execution times proportional to the size of the problem, but gg has much worse behavior than that. Bobby Treat -----Original Message----- From: Andrzej Kozlowski [mailto:andrzej at platon.c.u-tokyo.ac.jp] To: mathgroup at smc.vnet.net Subject: [mg34925] [mg34905] Re: [mg34858] A friendly challenge: Generalized Partition Here is my first (and only) attempt, which probably does not quite match yours but comes close enough (considering the amount of time I can spare for this). kk[ls_, t_] := With[{w = FoldList[Plus, 0, t]}, Map[Take[ls, #] &, Transpose[{Drop[w, -1] + 1, Rest[w]}]]] Tests on my 400 mghz PowerBook G4: In[3]:= a = Range[2000]; In[4]:= b = Table[Random[Integer, {1, 20}], {150}]; In[5]:= First[Timing[Do[gg[a, b], {100}]]] Out[5]= 6.24 Second In[6]:= First[Timing[Do[kk[a, b], {100}]]] Out[6]= 0.35 Second Since gg was somewhat faster than on your machine I assume that my kk is slower than your function. Andrzej On Tuesday, June 11, 2002, at 06:00 PM, Mr. Wizard wrote: > In the 4.1 help browser, in Further Examples under Take, there is code > for a generalized partition function, called gg. This code is > somewhat long and extremely slow. I challenge you to duplicate the > functionality of this code (ignoring the ggCheckArgs condition), while > making it 1) as sort as possible, and/or 2) as fast as possible. > > Your function must be in good form, leaving no stray assignments, i.e. > using the appropriate scoping construct(s). > > For efficiency testing, I will use (where func is your function): > > a = Range[2000]; > b = Table[Random[Integer, {1, 20}], {150}]; > First[Timing[Do[func[a, b], {100}]]] > > I will post my versions after a little while. For reference, on my > machine, the function from the help files, omitting the ggCheckArgs > condition, takes 8 seconds; my fastest version takes 0.33 seconds. My > shortest version is 44 characters in length, and takes 0.94 seconds. > > Good luck! > > Paul > > > > Andrzej Kozlowski Toyama International University JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/