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