使用map和reduce计算数列的平均值没有必要,只需要使用unfold生成列表,再使用fold将其缩减为平均值即可:
mean n m = uncurry (/) . foldr g (0, 0) . unfoldr f $ n
where
f b | b > m = Nothing
| otherwise = Just (b, b+1)
g x (s,n) = (s+x, n+1)
一个高效的实现
这个结构(fold . unfold
)允许进行融合优化。特别有效的实现将会将生成列表的unfold与列表约简的fold融合在一起。在Haskell中,GHC通过流融合组合了这两个阶段(unfold == enumFromN
)和fold:
import Data.Vector.Unboxed
data Pair = Pair !Int !Double
mean :: Vector Double -> Double
mean xs = s / fromIntegral n
where
Pair n s = foldl' k (Pair 0 0) xs
k (Pair n s) x = Pair (n+1) (s+x)
main = print (mean $ enumFromN 1 (10^7))
编译器将两个函数组合成一个递归循环:
main_loop a d e n =
case ># a 0 of
False -> (# I# n, D# e #);
True -> main_loop (-# a 1) (+## d 1.0) (+## e d) (+# n 1)
这将在汇编语言中转换为goto
(编译器的C后端):
Main_mainzuzdszdwfoldlMzqzuloop_info:
leaq 32(%r12), %rax
cmpq %rax, 144(%r13)
movq %r12, %rdx
movq %rax, %r12
jb .L198
testq %r14, %r14
jle .L202
.L199:
movapd %xmm5, %xmm0
leaq -1(%r14), %r14
movsd .LC0(%rip), %xmm5
addq $1, %rsi
addsd %xmm0, %xmm6
movq %rdx, %r12
addsd %xmm0, %xmm5
jmp Main_mainzuzdszdwfoldlMzqzuloop_info
使用LLVM可以得到更高效但更加复杂的实现(速度大约快2倍)。
参考资料: 在Haskell中高效计算列表平均值
reduce
(也称为fold
)并不是mapreduce
(例如Google框架)。即使您事先对输入进行了map
,也不是。 - user395760