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 [EMAIL PROTECTED] _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
