Best recursion choice for "penultimax"

[Dr Mark H Phillips]

Thanks for your alternative solutions.  (I also take
Mark Jones' point that there was an error with some of my
initial solutions.)

On Mon, 2002-11-25 at 16:36, Mark P Jones wrote:
> To your three implementations, let me add another two.  If you are
> looking
> for the smallest possible definition, consider the following:
> 
>   import List
> 
>   penultimax1 :: Ord a => [a] -> a
>   penultimax1  = head . tail . sortBy (flip compare)
> 
> A little more algorithmic sophistication leads to the following
> alternative that can find the penultimax with only  n + log2 n
> comparisons (approx), where n is the length of the list.

Is this "n + log(2n)" or "n + (log n)^2" or perhaps "n + log_base_2 n"?

Also, how did you calculate this?  (I am new to O(.) calculations
involving lots of recursion (ie in functional languages))

> 
>   penultimax :: Ord a => [a] -> (a, a)
>   penultimax  = tournament . map enter
>    where enter x = (x, [])
> 
>          tournament [(x, xds)] = (x, maximum xds)
>          tournament others     = tournament (round others)
> 
>          round ((x,xds):(y,yds):others)
>                    | x>=y      = (x, y:xds) : rest
>                    | otherwise = (y, x:yds) : rest
>                      where rest = round others
>          round xs              = xs
> 
> 
> Neat algorithm eh?  But be careful ...

It is interesting!

> 
> | How do I work out which is best to use?  Is there
> | one clear "winner", or will they each have pros and
> | cons?
> 
> Some quick tests with Hugs +s on a example list that I constructed
> with 576 elements give food for thought:

Thanks for the idea of using "hugs +s".  I haven't seen this
before.

> 
>                       reductions     cells
>    my one liner          4035        11483
>    tournament            7053        12288
>    your penultimax      16715        20180
>    your penultimax2      7466        10344
>    your penultimax3      8605        13782

> Hope this helps (or at least, is entertaining :-)

Yes.  Thanks!

Mark.

-- 
Dr Mark H Phillips
Research Analyst (Mathematician)

AUSTRICS - smarter scheduling solutions - www.austrics.com

Level 2, 50 Pirie Street, Adelaide SA 5000, Australia
Phone +61 8 8226 9850
Fax   +61 8 8231 4821
Email mark@austrics.com.au