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/