在Haskell中实现有效的滑动窗口算法 [英] Implementing an efficient sliding-window algorithm in Haskell

问题描述

  windows n xz @（x： xs）
 |长度v < n = [] 
 |否则= v：windows n xs 
其中
v = take n xz 
  

我的问题是我认为复杂度是O（n * m），其中m是列表的长度，n是窗口大小。你为取一次倒数列表，另一次为长度，然后你将它列入基本的列表mn倍。看起来它可能比这更有效率，但是我对如何使它更加线性化不知所措。任何接收者？

解决方案

您可以从<$ c $使用 Seq c> Data.Sequence ，它在两端都有O（1）入队和出队：

 导入Data.Foldable（toList）
将合格的Data.Sequence导入为Seq 
导入Data.Sequence（（|>））
 
 windows :: Int  - > [a]  - > [[a]] 
 windows n0 = go 0 Seq.empty 
其中
 go n s（a：as）| n'< n0 =去'n''为
 | n'== n0 = toList s'：以'b $ b |去'n''否则= toList s''：转到n s''作为
其中
 n'= n + 1  -  O（1）
 s'= s |> a  -  O（1）
 s''= Seq.drop 1 s' -  O（1）
去_ _ [] = [] 
  

请注意，如果您将整个结果具体化，则算法必须为O（N * M），因为这是结果的大小。使用 Seq 只是以一个常数来提高性能。

使用示例：

 >>> windows [1..5] 
 [[1,2,3]，[2,3,4]，[3,4,5]] 
  

I needed an efficient sliding window function in Haskell, so I wrote the following:

windows n xz@(x:xs)
  | length v < n = []
  | otherwise = v : windows n xs
  where
    v = take n xz

My problem with this is that I think the complexity is O(n*m) where m is the length of the list and n is the window size. You count down the list once for take, another time for length, and you do it down the list of essentially m-n times. It seems like it can be more efficient than this, but I'm at a loss for how to make it more linear. Any takers?

解决方案

You can use Seq from Data.Sequence, which has O(1) enqueue and dequeue at both ends:

import Data.Foldable (toList)
import qualified Data.Sequence as Seq
import Data.Sequence ((|>))

windows :: Int -> [a] -> [[a]]
windows n0 = go 0 Seq.empty
  where
    go n s (a:as) | n' <  n0   =              go n' s'  as
                  | n' == n0   = toList s'  : go n' s'  as
                  | otherwise =  toList s'' : go n  s'' as
      where
        n'  = n + 1         -- O(1)
        s'  = s |> a        -- O(1)
        s'' = Seq.drop 1 s' -- O(1)
    go _ _ [] = []

Note that if you materialize the entire result your algorithm is necessarily O(N*M) since that is the size of your result. Using Seq just improves performance by a constant factor.

Example use:

>>> windows [1..5]
[[1,2,3],[2,3,4],[3,4,5]]

这篇关于在Haskell中实现有效的滑动窗口算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！