如何改善滚动总和实施？

Question

如何改进以下滚动总和实施？

type Buffer  = State BufferState (Maybe Double)
type BufferState = ( [Double] , Int, Int )

-- circular buffer    
buff :: Double -> Buffer 
buff newVal = do
  ( list, ptr, len) <- get
  -- if the list is not full yet just accumulate the new value
  if length list < len
    then do
      put ( newVal : list , ptr, len)
      return Nothing
    else do
      let nptr = (ptr - 1) `mod` len
          (as,(v:bs)) = splitAt ptr list
          nlist = as ++ (newVal : bs)
      put (nlist, nptr, len)
      return $ Just v

-- create intial state for circular buffer
initBuff l = ( [] , l-1 , l)

-- use the circular buffer to calculate a rolling sum
rollSum :: Double -> State (Double,BufferState) (Maybe Double)
rollSum newVal = do
  (acc,bState) <- get
  let (lv , bState' )  = runState (buff newVal) bState
      acc' = acc + newVal
  -- subtract the old value if the circular buffer is full
  case lv of
    Just x  -> put ( acc' - x , bState') >> (return $ Just (acc' - x))
    Nothing -> put ( acc' , bState')     >> return Nothing

test :: (Double,BufferState) -> [Double] -> [Maybe Double] -> [Maybe Double]
test state [] acc = acc
test state (x:xs) acc = 
  let (a,s) = runState (rollSum x) state
  in test s xs (a:acc)

main :: IO()
main = print $ test (0,initBuff 3) [1,1,1,2,2,0] []

Buffer使用State monad来实现循环缓冲区.rollSum再次使用State monad来跟踪滚动和值和循环缓冲区的状态.

• 我怎么能让这更优雅？
• 我想实现其他功能,如滚动平均值或差异,我该怎么做才能让这个变得容易？

谢谢!

编辑

我忘了提到我正在使用循环缓冲区,因为我打算在线使用此代码并在它们到达时处理更新 - 因此需要记录状态.就像是

newRollingSum = update rollingSum newValue 

Answer 1

我没有设法破译你的所有代码,但这是我将采取的解决这个问题的计划.首先,该计划的英文描述:

1. 我们需要n从每个索引开始的长度列表中的窗口.
   1. 制作任意长度的窗户.
   2. 截断长窗口n.
   3. 删除最后一个n-1,这将太短.
2. 对于每个窗口,添加条目.

这是我的第一个想法; 对于长度为3的窗户,这是一个很好的方法,因为步骤2在这么短的清单上很便宜.对于更长的窗口,您可能需要一种替代方法,我将在下面讨论; 但是这种方法的好处是可以顺利地推广到除了以外的功能sum.代码可能如下所示:

import Data.List

rollingSums n xs
    = map sum                              -- add up the entries
    . zipWith (flip const) (drop (n-1) xs) -- drop the last n-1
    . map (take n)                         -- truncate long windows
    . tails                                -- make arbitrarily long windows
    $ xs

如果你熟悉的"等式推理"的方式优化,你可能会看到,我们可以提高此功能的性能第一名:通过交换第一map和zipWith,我们可以生产函数具有相同的行为,但有map f . map gsubterm,可以替换map (f . g)为获得稍微减少的分配.

不幸的是,对于大的n,这会n在内循环中将数字加在一起; 我们宁愿简单地在窗口的"前面"添加值,并在"后面"减去一个值.所以我们需要变得更加棘手.这是一个新想法:我们将平行两次遍历列表,n分开.然后我们将使用一个简单的函数来获得列表前缀的滚动总和(无界窗口长度),即将scanl (+)此遍历转换为我们感兴趣的实际总和.

rollingSumsEfficient n xs = scanl (+) firstSum deltas where
    firstSum = sum (take n xs)
    deltas   = zipWith (-) (drop n xs) xs -- front - back

有一个转折,即scanl永远不会返回空列表.因此,如果您能够处理短列表很重要,那么您将需要另一个检查这些列表的等式.不要使用length,因为它会在开始计算之前强制将整个输入列表放入内存 - 这可能是致命的性能错误.而是在上一个定义上面添加如下所示的行:

rollingSumsEfficient n xs | null (drop (n-1) xs) = []

我们可以在ghci中尝试这两个.你会发现,他们并不十分具有相同的行为,你的:

*Main> rollingSums 3 [10^n | n <- [0..5]]
[111,1110,11100,111000]
*Main> rollingSumsEfficient 3 [10^n | n <- [0..5]]
[111,1110,11100,111000]

另一方面,实现更简洁,并且在它们在无限列表上工作的意义上是完全懒惰的:

*Main> take 5 . rollingSums 10 $ [1..]
[55,65,75,85,95]
*Main> take 5 . rollingSumsEfficient 10 $ [1..]
[55,65,75,85,95]