在Haskell中有效地计算列表的平均值

Question

我设计了一个计算列表均值的函数.虽然它工作正常,但我认为它可能不是最好的解决方案,因为它需要两个功能而不是一个.只用一个递归函数就可以完成这项工作吗？

calcMeanList (x:xs) = doCalcMeanList (x:xs) 0 0

doCalcMeanList (x:xs) sum length =  doCalcMeanList xs (sum+x) (length+1)
doCalcMeanList [] sum length = sum/length

Answer 1

你的解决方案很好,使用两个功能并不比一个好.您仍然可以将尾递归函数放在where子句中.

但是如果你想在一行中做到这一点:

calcMeanList = uncurry (/) . foldr (\e (s,c) -> (e+s,c+1)) (0,0)

Answer 2

关于你能做的最好的是这个版本:

import qualified Data.Vector.Unboxed as U

data Pair = Pair {-# UNPACK #-}!Int {-# UNPACK #-}!Double

mean :: U.Vector Double -> Double
mean xs = s / fromIntegral n
  where
    Pair n s       = U.foldl' k (Pair 0 0) xs
    k (Pair n s) x = Pair (n+1) (s+x)

main = print (mean $ U.enumFromN 1 (10^7))

它融合到Core中的最佳循环(你可以写的最好的Haskell):

main_$s$wfoldlM'_loop :: Int#
                              -> Double#
                              -> Double#
                              -> Int#
                              -> (# Int#, Double# #)    
main_$s$wfoldlM'_loop =
  \ (sc_s1nH :: Int#)
    (sc1_s1nI :: Double#)
    (sc2_s1nJ :: Double#)
    (sc3_s1nK :: Int#) ->
    case ># sc_s1nH 0 of _ {
      False -> (# sc3_s1nK, sc2_s1nJ #);
      True ->
        main_$s$wfoldlM'_loop
          (-# sc_s1nH 1)
          (+## sc1_s1nI 1.0)
          (+## sc2_s1nJ sc1_s1nI)
          (+# sc3_s1nK 1)
    }

以下组装:

Main_mainzuzdszdwfoldlMzqzuloop_info:
.Lc1pN:
        testq %r14,%r14
        jg .Lc1pQ
        movq %rsi,%rbx
        movsd %xmm6,%xmm5
        jmp *(%rbp)
.Lc1pQ:
        leaq 1(%rsi),%rax
        movsd %xmm6,%xmm0
        addsd %xmm5,%xmm0
        movsd %xmm5,%xmm7
        addsd .Ln1pS(%rip),%xmm7
        decq %r14
        movsd %xmm7,%xmm5
        movsd %xmm0,%xmm6
        movq %rax,%rsi
        jmp Main_mainzuzdszdwfoldlMzqzuloop_info

基于Data.Vector.例如,

$ ghc -Odph --make A.hs -fforce-recomp
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...
$ time ./A
5000000.5
./A  0.04s user 0.00s system 93% cpu 0.046 total

请参阅统计包中的高效实现.

Answer 3

当我看到您的问题时，我立即想到“您想在那儿折！”

可以肯定的是，之前在StackOverflow上也曾提出过类似的问题，并且此答案具有非常出色的解决方案，您可以在诸如GHCi的交互式环境中进行测试：

import Data.List

let avg l = let (t,n) = foldl' (\(b,c) a -> (a+b,c+1)) (0,0) l 
            in realToFrac(t)/realToFrac(n)

avg ([1,2,3,4]::[Int])
2.5
avg ([1,2,3,4]::[Double])
2.5

Answer 4

虽然我不确定将其编写在一个函数中是否是“最佳”，但可以按如下方式完成：

如果您提前知道长度（这里称之为“n”），那么就很容易 - 您可以计算每个值“添加”到平均值的量；这将是值/长度。自从avg(x1, x2, x3) = sum(x1, x2, x3)/length = (x1 + x2 + x3)/3 = x1/3 + x2/3 + x2/3

如果你事先不知道长度，那就有点棘手了：

假设我们{x1,x2,x3} 在不知道其 n=3 的情况下使用该列表。

第一次迭代将只是 x1 （因为我们假设它唯一的 n=1）第二次迭代将x2/2 现有平均值相加并除以 2，所以现在我们有x1/2 + x2/2

第三次迭代后，我们有 n=3，我们希望有，x1/3 +x2/3 + x3/3 但我们有x1/2 + x2/2

所以我们需要乘以(n-1)并除以n得到x1/3 + x2/3 ，然后我们只需添加当前值（x3）除以n即可得到x1/3 + x2/3 + x3/3

一般来说：

给定 n-1 个项目的平均值（算术平均值 - avg），如果您想将一项（newval）添加到平均值中，您的方程将是：

avg*(n-1)/n + newval/n。该方程可以使用归纳法进行数学证明。

希望这可以帮助。

*请注意，此解决方案的效率比简单地对变量求和并除以总长度（如您在示例中所做的那样）的效率要低。