Personal tools

Sorting large arrays

From HaskellWiki

Jump to: navigation, search

An example of how to efficiently sort large arrays in native Haskell, using the uvector array type, and the uvector-algorithms package.

This is an in-place sort, using destructive updates in the ST (i.e. mutable memory) monad.

{-
 
Sort 10M floats efficiently in pure Haskell.
Uses uvector and uvector-algorithms.
 
-}
 
import Control.Monad.ST
import Data.Array.Vector
import Data.Array.Vector.Algorithms.Merge
 
main = do
    let e = runST (do
                v <- newMU (10^7) :: ST s (MUArr Float s)
                sort v
                readMU v 0)
    print e

It presents the smallest element of the array after sorting.

Compiling:

   ghc -O2 --make A.hs

Running:

   $ time ./A
   0.0
   ./A  1.22s user 0.04s system 98% cpu 1.278 total