5

我试图编写代码来计算函数花费的时间

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

功能构建列表：

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 时，无论列表有多长，它总是为零。

第二个：我想知道Real World 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
4

3 回答 3

11

问题一：

您的代码没有对列表进行排序！它只是将名称定义sortedlist为存在，quicksort list但在实际需要该值之前不会计算该名称。那是懒惰的评价。我们不会用这种语言做额外的工作。

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

您的选择

  • 使用seq. seq具有类型a -> b -> b并且具有将其第一个参数评估为所谓的“弱头范式”的行为。在这里，因为您想强制使用您可能想要使用的整个列表deepseq
  • 使用适当的基准测试包，如标准（首选且更容易）

问题2：

>>=是一元绑定运算符。在这里，它需要一个IO类型的动作IO a和一个函数a -> IO b，并将它们组合在一起以形成一个新的类型动作IO b。这与 do 表示法的作用相同。 foo >>= \x -> expr是一样的

 do x <- foo
    expr

事实上，do符号只是语法糖>>=

我不确定问题 3 中要问的是什么——也许它应该有自己的 Stackoverflow 问题。

于 2013-04-17T03:33:51.247 回答
4

difftime总是零，因为 Haskell 的惰性求值顺序已经完全优化掉了实际排序。您的程序中没有任何内容访问sortedlist，因此它甚至从未计算过。

正如另一个答案中所述，您可以强制您的程序使用一个名为fromsortedlist的有点神奇的函数进行计算。 等价于，除了它具有强制进行全面评估的副作用。deepseqControl.Deepseqdeepseq vidv

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

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

于 2013-04-17T03:46:41.883 回答
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
  • chronoNFdeepseq使用与其他一些答案讨论的相同策略进行评估。计时码表为不同的评估策略提供了其他功能。例如，我们可以评估为弱头范式，这实际上不会对列表进行完全排序。

计时码表也可以测量IO表达式，但处理这些表达式通常比非 IO 表达式简单得多。

于 2013-04-17T06:01:30.013 回答