0

如何捕获 Haskell 函数的运行时，例如，使用 GHC 编译的文件 Main.hs，其中包含对列表中的项目进行排序的函数“bubbleSort”：

 bubbleSort :: (Ord t) => [t] -> [t]
 bubbleSort a = loop (length a) bubble a 

 bubble :: (Ord t) => [t] -> [t]
 bubble (a:b:c) | a < b = a : bubble (b:c)
       | otherwise = b : bubble (a:c)
 bubble (a:[]) = [a] 
 bubble [] = []

 loop :: (Num a, Ord a) => a -> (t -> t) -> t -> t
 loop num f x | num > 0 =  loop (num-1) f x'
     | otherwise = x
     where x' = f x

注意：我知道这不是最有效的排序方法。

4

2 回答 2

3

你可以试试这样的标准， 

import System.Random
import Data.List
import Criterion.Main
import Criterion.Config


bubbleSort :: (Ord t) => [t] -> [t]
bubbleSort a = loop (length a) bubble a 

loop :: (Num a, Ord a) => a -> (t -> t) -> t -> t
loop num f x 
    | num > 0 =  loop (num-1) f x'
    | otherwise = x
        where x' = f x

bubble :: (Ord t) => [t] -> [t]
bubble (a:b:c) | a < b = a : bubble (b:c)
               | otherwise = b : bubble (a:c)
bubble (a:[]) = [a] 
bubble [] = []

randomlist :: Int -> StdGen -> [Int]
randomlist n = take n . unfoldr (Just . random)

main = do 
    seed <- newStdGen 
    let 
        xs100  = randomlist 100  seed  
        xs500  = randomlist 500  seed 
        xs2500 = randomlist 2500 seed 
      in defaultMainWith defaultConfig (return ()) [
            bgroup "bubble" [
                bench "bubble 100"  $ nf bubble xs100
              , bench "bubble 500"  $ nf bubble xs500
              , bench "bubble 2500" $ nf bubble xs2500
              ],
            bgroup "bubble Sort" [
                bench "bubbleSort 100"  $ nf bubbleSort xs100
              , bench "bubbleSort 500"  $ nf bubbleSort xs500
              , bench "bubbleSort 2500" $ nf bubbleSort xs2500
              ]
            ]

而输出，

warming up
estimating clock resolution...
mean is 2.181457 us (320001 iterations)
found 41466 outliers among 319999 samples (13.0%)
  2428 (0.8%) low severe
  39038 (12.2%) high severe
estimating cost of a clock call...
mean is 105.7764 ns (13 iterations)

benchmarking bubble/bubble 100
mean: 5.174493 us, lb 5.158926 us, ub 5.190592 us, ci 0.950
std dev: 80.64570 ns, lb 70.99540 ns, ub 93.12886 ns, ci 0.950
variance introduced by outliers: 8.479%
variance is slightly inflated by outliers

benchmarking bubble/bubble 500
mean: 28.41568 us, lb 28.22828 us, ub 28.64927 us, ci 0.950
std dev: 1.071815 us, lb 843.6888 ns, ub 1.531296 us, ci 0.950
found 4 outliers among 100 samples (4.0%)
  2 (2.0%) high mild
  1 (1.0%) high severe
variance introduced by outliers: 34.577%
variance is moderately inflated by outliers

benchmarking bubble/bubble 2500
mean: 132.3620 us, lb 131.0149 us, ub 134.1072 us, ci 0.950
std dev: 7.802474 us, lb 6.333342 us, ub 11.58801 us, ci 0.950
found 1 outliers among 100 samples (1.0%)
  1 (1.0%) high severe
variance introduced by outliers: 56.487%
variance is severely inflated by outliers

benchmarking bubble Sort/bubbleSort 100
mean: 399.7690 us, lb 398.7208 us, ub 400.7847 us, ci 0.950
std dev: 5.291009 us, lb 4.761788 us, ub 5.961798 us, ci 0.950
variance introduced by outliers: 6.563%
variance is slightly inflated by outliers

benchmarking bubble Sort/bubbleSort 500
mean: 15.42273 ms, lb 15.26078 ms, ub 15.60196 ms, ci 0.950
std dev: 872.8984 us, lb 784.0365 us, ub 967.8269 us, ci 0.950
variance introduced by outliers: 54.470%
variance is severely inflated by outliers

benchmarking bubble Sort/bubbleSort 2500
collecting 100 samples, 1 iterations each, in estimated 48.56091 s
mean: 473.5322 ms, lb 472.0005 ms, ub 474.9877 ms, ci 0.950
std dev: 7.695022 ms, lb 6.700990 ms, ub 9.001423 ms, ci 0.950
found 2 outliers among 100 samples (2.0%)
  2 (2.0%) low mild
variance introduced by outliers: 9.408%
variance is slightly inflated by outliers
于 2013-04-02T17:44:29.223 回答
0

最简单、最简单的方法是，首先使用 编译文件ghc --make yourfile.hs，然后在 shell ⁄命令提示符下运行它> yourfile +RTS -s并检查统计信息打印输出。

该文件应以

{-# OPTIONS_GHC -O2 #-}

module Main 
where

并包含一个main类型的值IO ()，例如

main :: IO ()
main = print $ bubbleSort ([1..50]++[42])

要从中获得任何有意义的读数，您应该找出算法的经验增长顺序；只有一个数据点不会告诉你太多。

于 2013-04-02T17:49:58.057 回答