在Haskell中实现高效的滑动窗口算法

Question

我在Haskell中需要一个高效的滑动窗口函数,所以我写了以下内容:

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

我的问题是我认为复杂度是O(n*m),其中m是列表的长度,n是窗口大小.你倒计时列表一次take,另一次length,你在基本上mn次列表中.看起来它可能比这更有效,但我对如何使其更加线性感到茫然.任何接受者？

Answer 1

您可以使用Seqfrom Data.Sequence,其中O(1)入队并在两端出列:

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 _ _ [] = []

请注意,如果您实现整个结果,则算法必须为O(N*M),因为这是结果的大小.使用Seq只是通过恒定因子提高性能.

使用示例:

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

Answer 2

你不能比O(m*n)更好,因为这是输出数据结构的大小.

但是,如果颠倒操作顺序,则可以避免检查窗口的长度:首先创建n个移位列表,然后将它们压缩在一起.压缩将摆脱那些没有足够元素的东西.

import Control.Applicative
import Data.Traversable (sequenceA)
import Data.List (tails)

transpose' :: [[a]] -> [[a]]
transpose' = getZipList . sequenceA . map ZipList

荏苒列表的列表只是一个换位,但不像transpose从Data.List它扔掉,将有小于输出ñ元素.

现在可以轻松实现窗口功能:取m列表,每个列表移1,然后压缩它们:

windows :: Int -> [a] -> [[a]]
windows m = transpose' . take m . tails

也适用于无限列表.

Answer 3

首先让我们得到窗口而不用担心最后的短窗口：

import Data.List (tails)

windows' :: Int -> [a] -> [[a]]
windows' n = map (take n) . tails

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

现在我们想去掉短的而不检查每个的长度。

由于我们知道它们在最后，我们可能会像这样丢失它们：

windows n xs = take (length xs - n + 1) (windows' n xs)

但这并不是很好，因为我们仍然需要额外的时间通过 xs 来获得它的长度。它也不适用于您的原始解决方案所做的无限列表。

相反，让我们编写一个函数，使用一个列表作为标尺来测量从另一个列表中获取的数量：

takeLengthOf :: [a] -> [b] -> [b]
takeLengthOf = zipWith (flip const)

> takeLengthOf ["elements", "get", "ignored"] [1..10]
[1,2,3]

现在我们可以这样写：

windows :: Int -> [a] -> [[a]]
windows n xs = takeLengthOf (drop (n-1) xs) (windows' n xs)

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

也适用于无限列表：

> take 5 (windows 3 [1..])
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7]]

正如 Gabriel Gonzalez 所说，如果你想使用整个结果，时间复杂度并没有更好。但是如果你只使用一些窗口，我们现在设法避免做的工作take，并length在您不使用的人。

Answer 4

如果您想要 O(1) 长度，那么为什么不使用提供 O(1) 长度的结构呢？假设您不是从无限列表中查找窗口，请考虑使用：

import qualified Data.Vector as V
import Data.Vector (Vector)
import Data.List(unfoldr) 

windows :: Int -> [a] -> [[a]]
windows n = map V.toList . unfoldr go . V.fromList
 where                    
  go xs | V.length xs < n = Nothing
        | otherwise =
            let (a,b) = V.splitAt n xs
            in Just (a,b)

从向量到列表的每个窗口的对话可能会让您有些困扰，我不会冒险乐观地猜测，但我敢打赌性能会比仅列表版本更好。