在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 4 [1,2..100]）的长度调用mAverage。

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

Answer 1

下面是一个简单的基于列表的解决方案，虽然需要更多的内存，但它的惯用性和足够快。

import Data.List (tails) 

mavg :: Fractional b => Int -> [b] -> [b] 
mavg k lst = take (length lst-k) $ map average $ tails lst 
    where average = (/ fromIntegral k) . sum . take k 

该解决方案允许在移动窗口中使用任何功能而不是average。

以下解决方案不太普遍，但它在空间上不变，似乎是最快的。

import Data.List (scanl') 

mavg :: Fractional b => Int -> [b] -> [b] 
mavg k lst = map (/ fromIntegral k) $ scanl' (+) (sum h) $ zipWith (-) t lst 
    where (h, t) = splitAt k lst 

最后，使用一种冈崎的持久功能队列来保持移动窗口的解决方案。处理流式数据（如导管或管道）时确实有意义。

mavg k lst = map average $ scanl' enq ([], take k lst) $ drop k lst 
    where 
    average (l,r) = (sum l + sum r)/fromIntegral k 

    enq (l, []) x = enq ([], reverse l) x 
    enq (l, (_:r)) x = (x:l, r) 

而且因为它是在评论中提到原来的岗位，没有建档使用ghci。例如，您将无法在ghci中看到scanl'的任何好处。这样做的

Answer 2

以下是您的解决方案。

这个想法是扫描两个列表，其中一个平均窗口开始，另一个结束。获取列表尾端的成本与扫描我们正在跳过的部分一样多，而且我们不会复制任何内容。 （如果窗口大小通常很大，我们可以一起计算remaining_data以及统计sum initial_data）。

我们生成部分总和列表，如我的评论中所述，然后将它们除以窗口宽度得到平均值。

虽然slidingAverage计算有偏位置（窗口宽度向右）的平均值，centeredSlidingAverage计算居中平均值，使用左右半窗宽度。

import Data.List (splitAt, replicate) 

slidingAverage :: Int -> [Int] -> [Double] -- window size, source list -> list of averages 
slidingAverage w xs = map divide $ initial_sum : slidingSum initial_sum xs remaining_data 
    where 
    divide = (\n -> (fromIntegral n)/(fromIntegral w)) -- divides the sums by window size 
    initial_sum = sum initial_data 
    (initial_data, remaining_data) = splitAt w xs 

centeredSlidingAverage :: Int -> [Int] -> [Double] -- window size, source list -> list of averages 
centeredSlidingAverage w xs = slidingAverage w $ left_padding ++ xs ++ right_padding 
    where 
    left_padding = replicate half_width 0 
    right_padding = replicate (w - half_width) 0 
    half_width = (w `quot` 2) -- quot is integer division 

slidingSum :: Int -> [Int] -> [Int] -> [Int] -- window_sum before_window after_window -> list of sums 
slidingSum _ _ [] = [] 
slidingSum window_sum before_window after_window = new_sum : slidingSum new_sum new_before new_after 
    where 
    value_to_go = head before_window 
    new_before = tail before_window 
    value_to_come = head after_window 
    new_after = tail after_window 
    new_sum = window_sum - value_to_go + value_to_come 

当我尝试length $ slidingAverage 10 [1..1000000]，它需要不到一秒钟我的MBP。 Due to the laziness，centeredSlidingAverage需要大约相同的时间。

Answer 3

如果你想学习新的东西，你可以看看这个漂亮的解决方案移动平均的问题。它是由我的一个学生写的，所以我不会声称作者身份。我非常喜欢它，因为它非常短。这里唯一的问题是average函数。已知这些功能是不好的。相反，您可以使用Beautiful folds by Gabriel Gonzalez。是的，该功能只O（K）时间（其中k是窗口的大小）来计算窗口的平均值（我觉得更好，因为你可以面对浮点错误，如果你尝试添加到窗口只新元素并扣除最后）。哦，它也采用State单子:)

{-# LANGUAGE UnicodeSyntax #-} 

module MovingAverage where 

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

average :: (Foldable t, Fractional a) ⇒ t a → a 
average xs = sum xs/fromIntegral (length xs) 

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) [] 

UPD：后一些代码审查我注意到，这是没有必要使用折叠这里来计算平均值。你知道长度总是n，所以你可以把average函数放入where子句。

Answer 4

一个简单的方法也使用O（n）的复杂性

movingAverage :: (Fractional a) => Int -> [a] -> [a] 
movingAverage n _ | n <= 0 = error "non-positive argument" 
movingAverage n xs = fmap average $ groupBy n xs 
    where average xs' = sum xs'/fromIntegral (length xs') 

groupBy :: Int -> [a] -> [[a]] 
groupBy _ [] = [] 
groupBy n xs = go [] xs 
    where 
    go _ []  = [] 
    go l (x:xs') = (x:t) : go (x:l) xs' 
     where t = take (n-1) l