Am Samstag 15 August 2009 10:09:28 schrieb Peter Verswyvelen: > I was reading the introduction at > http://www.haskell.org/haskellwiki/Introduction > where the typical Haskell version of qsort is given > > qsort [] = [] > qsort (x:xs) = qsort > (filter<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html >#v:filter> (< x) xs) > ++<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:.> > [x] > ++<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:.> >qsort > (filter<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html >#v:filter> > (>=<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:& >gt;=>x ) xs > > which is then compared to the inplace C version, showing off how much > shorter the Haskell version is. > > However, the page also has a link to a "semi-direct" translation of the C > version, which then brings the user to all kinds of confusing threads and > texts, like > > *"**Unfortunately none of the above "real" quicksorts seems to compile as > given, when copy/pasted into ghci. Can someone fix? The "parallel" > quicksort gave error "unknown package concurrent" when I ran make in > quicksort/gransim. Has anyone got a functioning "real" quicksort that works > on copy/paste? The program below is working very very slowly. It's probably > slowsort... :o)"* > * > * > Furthermore the inplace versions of qsort in Haskell are IMO less readable > than the C version. > > I'm not sure but if I would be a beginner I might get confused by this.
Okay, the more direct translation of the C code ---------------------------------------------------------- import Data.Array.Base (unsafeRead, unsafeWrite) import Data.Array.ST import Control.Monad.ST myqsort :: STUArray s Int Int -> Int -> Int -> ST s () myqsort a lo hi | lo < hi = do let lscan p h i | i < h = do v <- unsafeRead a i if p < v then return i else lscan p h (i+1) | otherwise = return i rscan p l i | l < i = do v <- unsafeRead a i if v < p then return i else rscan p l (i-1) | otherwise = return i swap i j = do v <- unsafeRead a i unsafeRead a j >>= unsafeWrite a i unsafeWrite a j v sloop p l h | l < h = do l1 <- lscan p h l h1 <- rscan p l1 h if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1 | otherwise = return l piv <- unsafeRead a hi i <- sloop piv lo hi swap i hi myqsort a lo (i-1) myqsort a (i+1) hi | otherwise = return () ---------------------------------------------------------------------------------------- doesn't sacrifice performance for polymorphism (the C code isn't polymorphic either) - in my tests, it took less than twice the time the C code took to sort the same array, not too bad. It compiles as is, and if it satisfies readability requirements, somebody can put it on the wiki. > > It is often claimed that compiler technology will make it possible to > compile high level code into efficient low level code that is almost as > efficient as the C or asm routines. How does this apply to qsort today? If you give it a chance to optimise, it isn't too bad. The code from the wiki takes about three times as long as the code above, ** if it's compiled a) with -O2 and b) in a setting where it specialises to the appropriate unboxed array type, be it by giving {-# SPECIALISE #-} pragmas or by having the code in the same module as the use (with a good type, e.g. STUArray s Int Int) **. If you disable optimisations by requiring fully polymorphic code and only that, the factor is about 80. > > Cheers, > Peter Verswyvelen _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe