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)
• 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

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/

```

• Prev by Date: Re: Re: A friendly challenge: Generalized Partition
• Next by Date: RE: A friendly challenge: Generalized Partition
• Previous by thread: Re: Re: A friendly challenge: Generalized Partition
• Next by thread: RE: A friendly challenge: Generalized Partition