Haskell计算函数执行的时间

Question

我尝试编写代码来计算一个函数所花费的时间

list <- buildlist 10000 10000    
starttime <- getClockTime
let sortedlist = quicksort list
endtime <- getClockTime
let difftime = diffClockTimes endtime starttime

函数buildlist:

buildlist :: Int -> Int -> IO [Int]
buildlist n m = do
    seed <- getStdGen
    let l = randomRs (0, m) seed
    let list = take n l
    return list

函数快速排序:

quicksort [] = []
quicksort (x:xs) =
    let head = [a|a<-xs,a<=x]
        tail = [a|a<-xs,a>x]
    in quicksort head ++ [x] ++ quicksort tail

第一个问题:当我输出difftime时，无论列表有多长，它总是零。

第二个:我想知道真实世界Haskell代码中的">>="是什么意思。

getClockTime >>= ((TOD sec _) -> return sec)

第三:我写这个是为了从TimeDiff变量中获得tdSec和tdPicosec。有更简单的方法吗?

time <-((TimeDiff _ _ _ _ _ s ps) -> return [ ( a -> fromIntegral a :: Double ) s , ( a -> fromIntegral a :: Double ) ps ] ) difftime

Answer 1

问题1:

您的代码没有对列表进行排序!它简单地将名称sortedlist定义为quicksort list，但直到实际需要该值时才计算。这就是惰性求值。我们不用这种语言做额外的工作

由于基准测试是额外无用的工作(这就是重点)，这使得基准测试变得困难。

选择

• 使用seq。seq具有a -> b -> b类型，并具有将其第一个参数评价为"弱头范式"的行为。在这里，因为你想强制整个列表，你可能需要使用deepseq
• 使用合适的基准测试包，如criterion(首选和更容易)

问题2:

>>=是一元绑定操作符。这里，它采用IO a类型的IO动作和a -> IO b类型的函数，并将它们组合在一起，生成一个IO b类型的新动作。这和do符号是一样的。foo >>= x -> expr和

是一样的

 do x <- foo
    expr

事实上，do符号只是>>=

的语法糖

我不确定问题3问的是什么——也许它应该得到自己的Stackoverflow问题

Answer 2

difftime总是0，因为Haskell的惰性求值顺序已经完全优化了实际排序。在你的程序中没有任何东西访问sortedlist，所以它从来没有被计算过。

正如另一个答案中所述，您可以使用Control.Deepseq中的一个称为deepseq的有点神奇的函数来强制程序计算sortedlist。deepseq v等价于id，除了它有强制v完全求值的副作用。

starttime <- getClockTime
let sortedlist = quicksort list
endtime <- deepseq sortedlist getClockTime

至于你的第二个问题，是的，有一种更简单的方法来访问TimeDiff的字段。Data声明中的字段名是getter函数。因此，tdSec td获得td的秒数，tdPicosec td获得皮秒数。

Answer 3

要测量纯函数的求值时间，您可能对我的Chronograph包感兴趣:http://hackage.haskell.org/package/chronograph

下面是如何使用它的一个简短示例:

Prelude Data.Chronograph> :m Data.Chronograph Data.List
Prelude Data.Chronograph Data.List> let theList = reverse [1..1000]
Prelude Data.Chronograph Data.List> sum theList 
500500
Prelude Data.Chronograph Data.List> let timed = chronoNF (sort theList)
Prelude Data.Chronograph Data.List> measure timed
0.000062s
Prelude Data.Chronograph Data.List> head $ val timed
1

几点说明:

• 我计算原始theList的和，以强制其构建和反转。如果这里没有强制，则构建成本将归因于对传递到chronoNF
的表达式的求值。
• chronoNF使用与deepseq相同的策略进行评估，正如其他一些答案所讨论的那样。计时码表为不同的评估策略提供了其他功能。例如，我们可以评估为弱头正常形式，这实际上不会对列表进行完全排序。

chronograph也可以测量IO表达式，但它们通常比非io表达式处理起来简单得多。