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