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 を出力すると、リストの長さに関係なく常にゼロになります。

2 つ目: Real World Haskellのコードの ">>=" は何を意味するのだろうか。

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

3 番目: TimeDiff変数からtdSecとtdPicosecを取得するためにこれを記述します。もっと簡単な方法はありますか？

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

3 に答える 3

11

質問1：

あなたのコードはリストをソートしません! 名前を定義するだけですsortedlistがquicksort list、値が実際に必要になるまで計算されません。それが遅延評価です。この言語で余分な作業は行いません。

ベンチマークは余分な無駄な作業であるため (それがポイントです)、これはベンチマークを困難にします。

あなたの選択

  • を使用しseqます。 seqは型a -> b -> bを持ち、最初の引数をいわゆる「弱頭正規形」に評価する動作をします。ここでは、使用したいリスト全体を強制したいのでdeepseq
  • 基準のような適切なベンチマーク パッケージを使用します(推奨され、簡単です) 。

質問2：

>>=モナドバインド演算子です。ここでIOは type のアクションIO aと関数を取り、a -> IO bそれらを組み合わせて type の新しいアクションを作成しIO bます。これは do 記法と同じことを行います。 foo >>= \x -> exprと同じことです

 do x <- foo
    expr

実際、do記法は単なる構文糖衣です。>>=

質問 3 で何が尋ねられているのかわかりません。おそらく、独自の Stackoverflow の質問を取得する必要があります。

于 2013-04-17T03:33:51.247 に答える
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 に答える