haskell - 在 Haskell 中计算移动平均线

Question

我正在学习 Haskell，所以我尝试实现一个移动平均函数。这是我的代码:

mAverage :: Int-> [Int] -> [Float]
mAverage x a = [fromIntegral k / fromIntegral x | k <- rawAverage]
    where
    rawAverage = mAverage' x a a

-- First list contains original values; second list contains moving average computations
mAverage' :: Int -> [Int] -> [Int] -> [Int]
mAverage' 1 a b = b
mAverage' x a b = mAverage' (x - 1) a' b'
    where
    a' = init a
    b' = zipWith (+) a' (tail b)

用户调用 mAverage 时，每个平均值都有一个长度和值列表(例如 mAverage 4 [1,2..100] )。

但是，当我在输入 mAverage 4 [1,2..100000] 上运行代码时，我知道在 ghci 中需要 3.6 秒(使用 :set +s)并使用千兆字节的内存。这对我来说似乎非常低效，因为等效函数在 Python 中只需要几分之一秒。有什么方法可以让我的代码更有效率吗？

Answer 1

如果你想学习新的东西，你可以看看这个很好的移动平均问题解决方案。它是我的一个学生写的，所以我不会声称作者身份。我真的很喜欢它，因为它很短。这里唯一的问题是average功能。众所周知，这样的功能是不好的。相反，您可以使用 Beautiful folds by Gabriel Gonzalez .是的，这个函数需要 O(k) 计算窗口平均值的时间(其中 k 是窗口大小)(我发现它更好，因为如果您尝试仅向窗口添加新元素并减去最后一个元素，您可能会遇到浮点错误)。哦，它也使用State单子(monad):)

{-# LANGUAGE UnicodeSyntax #-}

module MovingAverage where

import           Control.Monad       (forM)
import           Control.Monad.State (evalState, gets, modify)

moving :: Fractional a ⇒ Int → [a] → [a]
moving n _  | n <= 0 = error "non-positive argument"
moving n xs = evalState (forM xs $ \x → modify ((x:) . take (n-1)) >> gets average) []
  where
    average xs = sum xs / fromIntegral n