時間測定

下のように、クイックソートの実行時間を調べためのrecordTime関数を定義。
qsortはリスト内包表記、
Qsortはfilter関数を使った見易い定義によるもの。
この二つで果たして実行時間は変わるのか！
と思ってやってみたけれど、どれも結果は
0s.....
比較できない.....おそらく遅延評価のため。
実際に値が使われないので、関数が評価されず、正しい時間が記録されない。

module Qsort where

import Data.Time.Clock

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort ls ++ [x] ++ qsort rs
    where
        ls = [ e | e <- xs , e < x]
        rs = [ e | e <- xs , e >= x]

qsort' :: Ord a => [a] -> [a]
qsort' [] = []
qsort' (x:xs) = myQsort rs ++ [x] ++ myQsort ls
    where
        rs = filter (<x) xs
        ls = filter (>=x) xs

recordTime :: (Num a,Enum a) => ([a] -> [a]) -> a -> IO ()
recordTime f n = do start <- getCurrentTime
                    r <- return $ f [n,(n-1)..0]
                    stop <- getCurrentTime
                    print $ diffUTCTime stop start

調べてみたら、正格評価関係の($!)関数が使えそう。

>:t ($!)
($!) :: (a -> b) -> a -> b

ふむ。
おそらく、第一引数にとる関数の処理を、遅延させずに評価してくれるのでしょう。
信じたい。
というわけで,この関数を使って書きなおしてみた。

module Qsort where
import Data.Time.Clock
import System.CPUTime

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort ls ++ [x] ++ qsort rs
    where
        ls = [ e | e <- xs , e < x]
        rs = [ e | e <- xs , e >= x]

qsort' :: Ord a => [a] -> [a]
qsort' [] = []
qsort' (x:xs) = myQsort rs ++ [x] ++ myQsort ls
    where
        rs = filter (<x) xs
        ls = filter (>=x) xs

recordTime :: (Num a,Enum a) => ([a] -> [a]) -> a -> IO [a]
recordTime f n = do start <- getCurrentTime --getCPUTime
                    r <- return $! f [n,(n-1)..0]
                    stop <- getCurrentTime --getCPUTime
                    print $ diffUTCTime stop start
                                -- stop - start
                    return r

コメント内の関数は、CPU時間を利用する際のものです。
でも、このままでも十分使える。