Re: Re: A friendly challenge: Generalized Partition
- To: mathgroup at smc.vnet.net
- Subject: [mg34926] Re: [mg34905] Re: [mg34858] A friendly challenge: Generalized Partition
- From: Andrzej Kozlowski <andrzej at platon.c.u-tokyo.ac.jp>
- Date: Thu, 13 Jun 2002 02:38:14 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Re-reading mine and your message I noticed something I originally
missed, and tha tis that it is extremely easy to beat the performance of
your best function, provided you keep to your promise of using the test
you mentioned in your message.
In[1]:=
kk[ls_, t_] :=kk[ls, t] =
With[{w = FoldList[Plus, 0, t]},
Map[Take[ls, #] &, Transpose[{Drop[w, -1] + 1, Rest[w]}]]]
In[2]:=
a = Range[2000];
In[3]:=
b = Table[Random[Integer, {1, 20}], {150}];
In[4]:=
First[Timing[Do[kk[a, b], {100}]]]
Out[4]=
0.01 Second
Andrzej
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
On Wednesday, June 12, 2002, at 03:15 PM, Andrzej Kozlowski wrote:
> 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
>>
>>
>>
>>
>
>
>