在代码审查中,我回答了一个关于 naive Haskell fizzbuzz solution 的问题。通过建议 iterates forward 的实现,避免了增加素数的二次成本和(几乎)完全丢弃模除法。这是代码:
fizz :: Int -> String
fizz = const "fizz"
buzz :: Int -> String
buzz = const "buzz"
fizzbuzz :: Int -> String
fizzbuzz = const "fizzbuzz"
fizzbuzzFuncs = cycle [show, show, fizz, show, buzz, fizz, show, show, fizz, buzz, show, fizz, show, show, fizzbuzz]
toFizzBuzz :: Int -> Int -> [String]
toFizzBuzz start count =
let offsetFuncs = drop (mod (start - 1) 15) fizzbuzzFuncs
in take count $ zipWith ($) offsetFuncs [start..]
作为进一步的提示,我建议使用
Data.List.unfoldr
重写它。 . unfoldr
version 是对这段代码的明显、简单的修改,所以我不会在这里输入它,除非寻求回答我的问题的人坚持认为这很重要(代码审查中的 OP 没有剧透)。但我确实对 unfoldr
的相对效率有疑问。与 zipWith
相比的解决方案一。虽然我不再是 Haskell 新手,但我也不是 Haskell 内部结构方面的专家。一个
unfoldr
解决方案不需要 [start..]
无限列表,因为它可以简单地从 start
展开.我的想法是zipWith
解决方案不会记住 [start..]
的每个连续元素正如它所要求的那样。每个元素都被使用和丢弃,因为没有保留对 [start..] 头部的引用。所以没有比 unfoldr
更多的内存消耗。 . unfoldr
性能的担忧最近的补丁使其始终内联,这是在我尚未达到的水平上进行的。 所以我认为两者在内存消耗上是相当的,但不知道相对性能。希望更多消息灵通的 Haskellers 可以引导我理解这一点。
unfoldr
用于生成序列似乎是一件很自然的事情,即使其他解决方案更具表现力。我只知道我需要更多地了解它的实际性能。 (出于某种原因,我发现 foldr
在该级别上更容易理解)备注 :
unfoldr
对 Maybe
的使用是我什至开始调查该问题之前发生的第一个潜在性能问题(也是我完全理解的优化/内联讨论的唯一一点)。所以我可以不用担心 Maybe
马上(鉴于 Haskell 的最新版本)。
最佳答案
作为负责 zipWith
的最近实现变化的人和 unfoldr
,我想我可能应该尝试一下。我不能那么容易地比较它们,因为它们是非常不同的功能,但我可以尝试解释它们的一些属性和变化的意义。unfoldr
内联
旧版unfoldr
(在 base-4.8
/GHC 7.10 之前)在顶层是递归的(它直接调用自身)。 GHC 从不内联递归函数,所以 unfoldr
从未内联。结果,GHC 无法看到它如何与传递的函数进行交互。最令人不安的影响是传入的函数类型为 (b -> Maybe (a, b))
。 , 实际上会产生 Maybe (a, b)
值,分配内存来保存 Just
和 (,)
构造函数。通过重组 unfoldr
作为“worker”和“wrapper”,新代码允许 GHC 内联它并(在许多情况下)将它与传入的函数融合,因此额外的构造函数被编译器优化剥离。
例如,在 GHC 7.10 下,代码
module Blob where
import Data.List
bloob :: Int -> [Int]
bloob k = unfoldr go 0 where
go n | n == k = Nothing
| otherwise = Just (n * 2, n+1)
用
ghc -O2 -ddump-simpl -dsuppress-all -dno-suppress-type-signatures
编译导致核心$wbloob :: Int# -> [Int]
$wbloob =
\ (ww_sYv :: Int#) ->
letrec {
$wgo_sYr :: Int# -> [Int]
$wgo_sYr =
\ (ww1_sYp :: Int#) ->
case tagToEnum# (==# ww1_sYp ww_sYv) of _ {
False -> : (I# (*# ww1_sYp 2)) ($wgo_sYr (+# ww1_sYp 1));
True -> []
}; } in
$wgo_sYr 0
bloob :: Int -> [Int]
bloob =
\ (w_sYs :: Int) ->
case w_sYs of _ { I# ww1_sYv -> $wbloob ww1_sYv }
融合
另一个更改为
unfoldr
正在重写它以参与“折叠/构建”融合,这是 GHC 列表库中使用的优化框架。 “折叠/构建”融合和更新的、不同平衡的“流融合”(在 vector
库中使用)的想法是,如果列表由“好的生产者”生成,则由“好的转换器”转换,并被“好消费者”消费,那么列表 conses 根本不需要分配。老unfoldr
不是一个好的制作人,所以如果你制作了一个带有 unfoldr
的列表并将其与 foldr
一起使用,随着计算的进行,列表的各个部分将被分配(并立即变成垃圾)。现在,unfoldr
是一个很好的生产者,所以你可以写一个循环,比如说,unfoldr
, filter
, 和 foldr
,而不是(必然)分配任何内存。例如,给定上述
bloob
的定义和严厉的{-# INLINE bloob #-}
(这东西有点脆弱;好的生产者有时需要明确内联才能好),代码hooby :: Int -> Int
hooby = sum . bloob
编译到 GHC 核心
$whooby :: Int# -> Int#
$whooby =
\ (ww_s1oP :: Int#) ->
letrec {
$wgo_s1oL :: Int# -> Int# -> Int#
$wgo_s1oL =
\ (ww1_s1oC :: Int#) (ww2_s1oG :: Int#) ->
case tagToEnum# (==# ww1_s1oC ww_s1oP) of _ {
False -> $wgo_s1oL (+# ww1_s1oC 1) (+# ww2_s1oG (*# ww1_s1oC 2));
True -> ww2_s1oG
}; } in
$wgo_s1oL 0 0
hooby :: Int -> Int
hooby =
\ (w_s1oM :: Int) ->
case w_s1oM of _ { I# ww1_s1oP ->
case $whooby ww1_s1oP of ww2_s1oT { __DEFAULT -> I# ww2_s1oT }
}
没有列表,没有
Maybe
s,没有对;它执行的唯一分配是Int
用于存储最终结果(I#
到 ww2_s1oT
的应用)。可以合理地预期整个计算将在机器寄存器中执行。zipWith
zipWith
有一个奇怪的故事。它有点笨拙地适合折叠/构建框架(我相信它在流融合方面工作得更好)。可以制作zipWith
fuse 与它的第一个或第二个列表参数,并且多年来,列表库试图使其与其中任何一个融合,如果其中一个是一个好的生产者。不幸的是,使其与第二个列表参数融合可能会使程序在某些情况下的定义更少。即,使用 zipWith
的程序在没有优化的情况下编译时可以正常工作,但在使用优化编译时会产生错误。这不是一个很好的情况。因此,截至 base-4.8
, zipWith
不再尝试与它的第二个列表参数融合。如果你想让它与一个好的生产者融合,那个好的生产者最好在第一个列表参数中。具体来说,
zipWith
的引用实现导致期望,例如,zipWith (+) [1,2,3] (1 : 2 : 3 : undefined)
会给[2,4,6]
,因为它一到达第一个列表的末尾就停止了。与之前的 zipWith
实现,如果第二个列表看起来像这样,但由一个好的生产者制作,并且如果 zipWith
碰巧与它融合而不是第一个列表,然后它就会繁荣起来。
关于performance - 展开器与 zipWith 的效率,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32521479/