在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