Tor*_*iel 33 performance haskell
我目前正在学习Haskell(通过交易成为程序员,但这是我第一次尝试使用函数式语言).
我想编写一个扫描列表的函数,并返回该列表的最小和最大元素.排序Prelude的功能minimum和maximum做法,但两者同时进行.我想出了以下代码:
import Data.List
-- Declaration of rand
minMax :: [Int] -> Maybe (Int, Int)
minMax [] = Nothing
minMax (x:xs) = Just (foldl' f (x, x) xs)
where
f (a, b) c = (if c < a then c else a, if c > b then c else b)
Run Code Online (Sandbox Code Playgroud)
rand是一个生成无限数字列表的函数.问题是,当我追加以下main功能时:
main = print $ minMax $ take 1000000 $ rand 7666532
Run Code Online (Sandbox Code Playgroud)
使用profiling编译并运行所有这些,它显示它使用超过200 MB的内存,所以它绝对不是一个恒定空间函数(我希望它是).
问题是为什么以及我应该改变什么来解决它.据我所知foldl',从左侧折叠列表(它生成的方式相同)并且不是懒惰的,所以我不明白为什么内存使用率如此之高.我很确定这minMax是不正确的功能,只需打印上述列表即可
main = print $ take 1000000 $ rand 7666532
Run Code Online (Sandbox Code Playgroud)
给我1MB的使用量,这是我理解和期待的.
Bak*_*riu 26
请注意,foldl'强制累加器为弱头正常形式.由于累加器是一个元组,因此它不会强制对元组的两个元素进行求值.
如果明确强制使用这两个元素,则会得到一个常量空间函数:
f (a, b) c = a `seq` b `seq` (if c < a then c else a, if c > b then c else b)
Run Code Online (Sandbox Code Playgroud)
在原来的计划正在构建的类型的元组:(<thunk>, <thunk>)和每一次f应用于您只需建立一个元组与越来越大的thunk.当最后通过强制print调用消耗时show,对元组进行全面评估,并在此时进行所有比较.
在此时使用seq您强制f评估比较,因此在执行比较之前评估累加器中包含的thunk.因此,结果是存储在累加器中的thunk具有恒定的大小.
什么foldl'只是避免建立thunk : f (f (f ...) y) x.
Jubobs建议的另一种避免明确使用的解决方案seq是使用具有严格字段的数据类型:
data Pair a b = Pair !a !b
deriving Show
Run Code Online (Sandbox Code Playgroud)
所以代码将成为:
minMax :: [Int] -> Maybe (Pair Int Int)
minMax [] = Nothing
minMax (x:xs) = Just (foldl' f (Pair x x) xs)
where
f (Pair a b) c = Pair (if c < a then c else a) (if c > b then c else b)
Run Code Online (Sandbox Code Playgroud)
这完全避免了thunk.
oba*_*adz 12
该seq函数主要用于foldl'强制其第一个参数被评估为WHNF(弱头范式).
正如这里所解释的,WHNF评估在每次应用构造函数时都会停止.(a, b)因此,在WHNF始终,即使a和b是的thunk,因为你打的元组构造(,)越来越之前a和b.
因此,尽管使用了foldl'以下方法,但这个空间泄漏:
foldl' (\ (a, b) x -> (a + x, b + x)) (0, 1) [1..1000000]
Run Code Online (Sandbox Code Playgroud)
但这不是:
foldl' (\ (a, b) x -> a `seq` b `seq` (a + x, b + x)) (0, 1) [1..10000000]
Run Code Online (Sandbox Code Playgroud)
使用-XBangPatterns扩展名有时也很方便写这个:
foldl' (\ (!a, !b) x -> (a + x, b + x)) (0, 1) [1..10000000]
Run Code Online (Sandbox Code Playgroud)
| 归档时间: |
|
| 查看次数: |
1227 次 |
| 最近记录: |