﻿

# 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)
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