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
(filterhttp://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
(filterhttp://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
