為什麼這幾種fib函式的效能差異如此之大?

時間 2021-05-31 10:07:26

1樓:九瓜

let y = e1 in let f x = e2 in ... (f u) ... (f v) ...

其中在 e2 裡面會用到 y。這裡 e1 的計算和 x 是無關的,所以在 f u 和 f v 的計算中可以共享同乙個 e1 的值。值得注意的是,full laziness 優化同時改變了時間和空間效率,因為 e1 的值必須在計算 f u 和 f v 之間一直留駐記憶體。

這是以空間換時間的典型例子,因該視具體情況選擇性使用。

更新:我又仔細看了一下 eta expansion 在這裡面的作用,把 fib1 改成

fib1 = (!!) (map fib' [0..]) where fib' = ...

試過之後,效率和原 fib1 一樣(我之前做的試驗有誤)。編譯時如果不做任何優化,那麼 fib1 本身並非是乙個函式,依據 WHNF (weak head normal form) 的要求對它先進行求值(以下用 let 表示求值環境):

fib1 = (!!) (map fib' [0..]) where fib'let fib'l = map fib' [0in (!!) l

這時候需要將 (!!) 的定義代入(來自 Haskell Report):

(!!) :: [a] -> Int -> a

xs !! n | n < 0 = error "Prelude.!!: negative index"error "Prelude.!!: index too large"

(x:_) !! 0 = x

(_:xs) !! n = xs !! (n-1)

簡單寫就是:

(!!) xs n = if n < 0 then ... else case xs of { ->

將 (!!) 的定義代入 fib1 可以得到它的 WHNF:

fib1 = let fib'l = map fib' [0in \n -> if n < 0 then ... else case l of { ->

我們可以比較一下 fib2(因為已經是 WHNF 了,所以以下化簡純粹是為了有個對照):

fib2 = \x -> (!!) (map fib' [0..]) x where fib'x -> let fib'l = map fib' [0in (!!) l x

= \x -> let fib'l = map fib' [0in if x < 0 then ... else case l of { ->

這時候可以看出兩者的差別就在於 fib' 和 l 的定義是在 \x -> .. 閉包內,還是在外。而 full laziness 優化所做的就是將 fib2 轉換成 fib1 的形式。

2樓:

對了,談效能的時候不考慮編譯選項嗎?

1和2的寫法,在不開編譯優化的時候有不一樣,但是開了 -O後是一樣的。

(還是看TRACE)

$ ghc fib.hs

[1 of 1] Compiling Mainfib.hs, fib.o )

Linking fib ...

$ ./fib 1 443

2105

$ ./fib 2 443

2101

2105

$ ghc -O fib.hs

[1 of 1] Compiling Mainfib.hs, fib.o )

Linking fib ...

$ ./fib 1 402

1435

$ ./fib 2 402

1435

可以看到在開啟O優化後,2和1在執行上已經一樣了,說明這兩個寫法「根本」上是等效的,只是差別比較深,需要優化。

但是我更感興趣的是求值順序也不同了,這個倒是很意外。

另外3和4的寫法在O下也有改變,好像把0和1兩個常數部分給記住了。

3樓:rainoftime

Haskell並不是快取所有函式的結果。

惰性求值的「快取」只是對按名呼叫的改進。

Desuger之後

(map

fib'[0

..]!!)

->(!!

)(mapfib'[0

..])

mapfib'[0

..]!!x

->\x

->(!!

)(mapfib'[0

..])

x第二個的Expression在Lambda Expression裡面,每次Lambda呼叫產生新的例項。開-O2優化之後可能也可以「提取」出來,所以和第乙個差不多快

用trace試一下 ,fib1每個fib n都只算了1次,考慮到!!是的,所以應該是。,而fib2則不然(有重複計算)。

第三、四個版本和下面的是等價的,為,map fib' [0..]幾乎不起作用。

fib::

Int->

Integer

fib0=1

fib1=1

fibn

=fib(n

-1)+

fib(n-2)

為什麼這幾年鄭伊健的人氣越來越差?

一根黃山 這是沒有辦法的事情,跟個人性格還有遭遇有關。鄭伊健早年是和大部分香港藝人的經歷一樣,TVB電視劇集演員出道,然後解約進入影視圈,順帶著出幾張唱片,不過那個時候鄭伊健只能算是電影圈的新人,並沒有什麼名氣,被王晶硬捧了幾部電影後還是沒什麼起色,一直到 古惑仔 找到了他,成就了鄭伊健!那段時間鄭...

為什麼蘋果的機械硬碟效能這麼差 ,卡到完全不能用,以前用windows都是機械硬碟也沒有這麼差

螃蟹在B0我的殼 受眾面問題啊 windows多少廠商在用?什麼五花八門的配置都有,當然會考慮到效能較差的一些機械硬碟,以保證系統流暢執行。Mac OS只給蘋果自家電腦用優化當然只基於自己的配置,這幾年的mac應該全系標配固態了,新版本的Mac OS自然不用考慮對機械盤的優化。樓主說的蘋果機械硬碟效...

為什麼沒有人把錳,鎢,鈦,鐵幾種高效能的金屬做刀?非要用普通的鋼材。?

路人一一假 我是廚房刀具diy愛好者,您說的這幾種我們廚刀圈經常用,錳鋼為代表的汽車承重弓子板加工成廚刀是普遍且便宜實用的一種,高鎢鋼硬度太高不容易加工打磨,廚刀極少用,一般用來做鑽頭。鈦合金有用的如TC21和TC19,硬度不高,一般在HrC三四十但保持性都很好,不生鏽,但是打磨也很難,高階的自製廚...