Re: Python sol'n to qotw 23 (parens)

Andrew Dalke wrote:
> This is a recursive solution using generators.  The
> idea is essentially the same as Bill Tuckers and also
> done by Matthew Walton in his Haskell solution (and
> perhaps others).

Seems to be a fairly elegant way to do it... I was surprised actually by 
how clean the Perl translation I did of my implementation was, although 
it's probably not how I would have done it if I'd done it in Perl to 
start with.

> Here's what I get for timings on my 1GHz PowerBook G4.
> I tried with both the --count option and by generating
> all the output > /dev/null (wanted to see how much I/O
> overhead there was).  I ran them on the command-line
> so the 0.12s or so is basically the startup costs.
> 
>                               Output
>                   Count     >/dev/null  Bill's
> Size    Count    Time(in s)   (in s)    times
> ----   ------    ------     ------    ------
>  0          0      0.13       0.14      0.08
>  1          1      0.12       0.12      0.06
>  2          2      0.12       0.12      0.18
>  3          5      0.12       0.12      0.06
>  4         14      0.12       0.12      0.11
>  5         42      0.12       0.12      0.10
>  6        132      0.12       0.12      0.09
>  7        429      0.13       0.13      0.15
>  8       1430      0.15       0.15      0.31
>  9       4862      0.22       0.24      0.57
> 10      16796      0.49       0.54      1.57
> 11      58786      1.52       1.82      6.04
> 12     208012      5.41       6.42     19.62
> 13     742900     22.39      24.77     64.13
> 14    2674440     90.73      89.12    228.41
> 15    9694845    291.84     343.68      n/a
> 
> Bill's code is about 3 times slower than mine
> for large values.  For small value it's hard
> to tell because Perl has a quicker startup time
> than Python.
> 
> Matthew's compiled Haskell noprint time for 12
> elements took 1.5 seconds or about 4 times faster.
> However, his print > /dev/null version is 3.1
> seconds or only twice as fast.

I suspect that the fold operation I do on the results list in order to 
print it is quite expensive, although it's the fastest way I can think 
of to manage it without delving into the realms of unsafePerformIO.

Interestingly enough, I ran my optimised build for 15 redirected to 
/dev/null and got this:

real    1m57.645s
user    1m48.180s
sys     0m3.780s

also known as 117.65 seconds, which is about 40% of your time for count 
only mode. I'd be smug, but I can't be because your Python wasn't 
compiled. I'd be curious to know if the Python implementation for Parrot 
is complete enough to run this code, and if so is it any faster?

What surprised me the most about this time is that the time with output was

real    23m54.900s
user    2m49.990s
sys     0m55.220s

Which is insane. Printing things out is obviously a bad idea.

> Matthew said the 12 case generated over 200,000
> solutions, which is what I get.  I don't see
> any other posts which list the sizes.  I
> would like to have the double check.

That's the exact size I got, which implies we both got the solution 
right... or at least wrong in exactly the same way :-)