Guest User

Untitled

a guest
Dec 21st, 2013
247
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. {-# OPTIONS -O2 #-}
  2. import System.CPUTime (getCPUTime)
  3. import Foreign (Ptr, peekElemOff, pokeElemOff, mallocArray)
  4. import Control.Monad (forM_)
  5. import System.Exit (exitFailure)
  6.  
  7. pushDown :: Ptr Int -> Int -> Int -> IO ()
  8. pushDown h pos n
  9.   | 2*pos + 1 < n = do
  10.       let j' = 2*pos + 1
  11.      atJ' <- peekElemOff h j'
  12.      (j, atJ) <- if j'+1<n
  13.                   then do atJ'inc <- peekElemOff h (j'+1)
  14.                           return $ if atJ'inc > atJ'
  15.                                    then (j'+1, atJ'inc)
  16.                                    else (j', atJ')
  17.                   else return (j', atJ')
  18.       atPos <- peekElemOff h pos
  19.       if atPos >= atJ
  20.       then return ()
  21.       else do pokeElemOff h j atPos
  22.               pokeElemOff h pos atJ
  23.               pushDown h j n
  24.   | otherwise = return ()
  25.  
  26. main = do
  27.   start <- getCPUTime
  28.   let n = 10000000
  29.   h <- mallocArray n
  30.   forM_ [0..n-1] $ \i -> pokeElemOff h i i
  31.   forM_ [n`div`2,n`div`2-1..0] $ \i -> pushDown h i n
  32.   forM_ [n-1,n-2..1] $ \i -> do
  33.          x <- peekElemOff h 0
  34.          peekElemOff h i >>= pokeElemOff h 0
  35.          pokeElemOff h i x
  36.          pushDown h 0 i
  37.   forM_ [0..n-1] $ \i -> do x <- peekElemOff h i
  38.                             if i == x then return () else exitFailure
  39.   end <- getCPUTime
  40.   putStrLn $ "Done in " ++ (show $ (end - start) `div` 10^9)
RAW Paste Data