计算Haskell中的移动平均线 [英] Computing Moving Average in Haskell

问题描述

我正在学习Haskell，因此我尝试实现移动平均功能.这是我的代码:

I'm working on learning Haskell, so I tried to implement a moving average function. Here is my code:

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

where the user calls mAverage with a length for each average and the list of values (e.g. mAverage 4 [1,2..100]).

但是，当我在输入mAverage 4 [1,2..100000]上运行代码时，我得到ghci(使用:set +s)需要3.6秒，并使用了1 GB的内存.在我看来，这是非常低效的，因为等效功能在Python中仅需不到一秒钟的时间.有什么方法可以使我的代码更高效?

However, when I run the code on the input mAverage 4 [1,2..100000], I get that it takes 3.6 seconds in ghci (using :set +s) and uses a gigabyte of memory. This seems very inefficient to me, as the equivalent function takes a fraction of a second in Python. Is there some way that I could make my code more efficient?

推荐答案

这是一个简单的基于列表的解决方案，虽然需要更多的内存，但它是惯用的并且足够快.

Here is a straightforward list-based solution which is idiomatic and fast enough, though requires more memory.

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.

This solution allows to use any function instead of average in a moving window.

以下解决方案的通用性较差，但在空间上是恒定的，似乎是最快的解决方案.

The following solution is less universal but it is constant in space and seems to be the fastest one.

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 

最后，该解决方案使用Okasaki的持久功能队列来保持移动窗口.处理管道或管道之类的流数据时，它确实有意义.

Finally, the solution which uses a kind of Okasaki's persistent functional queue, to keep the moving window. It does make sense when dealing with streaming data, like conduits or pipes.

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'的任何好处.

And as it was mentioned in comments to the original post, do not use ghci for profiling. For example, you won't be able to see any benefits of scanl' in ghci.

这篇关于计算Haskell中的移动平均线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！