一种滑动window

Question

这个函数来自一些计算有限序列卷积的代码。

window n k = [ drop (i-k) $ take i $ [1..n] | i <- [1..(n+k)-1] ]

*Main> window 4 6
[[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4],[1,2,3,4],[2,3,4],[3,4],[4]]

它在长度 n 的序列上滑动 window 长度 k，其中 k 可以大于 n。

代码在源列表中调用 take 和 drop 大约 n+k 次，因此它似乎至少具有二次复杂度。

很明显，不用列表理解也可以这样写：

window n k = map (\i -> (drop (i-k) . take i) [1..n]) [1..(n+k)-1]

有更好的方法吗？

编辑： 全套示例，按要求提供。

Prelude> window 4 4
[[1],[1,2],[1,2,3],[1,2,3,4],[2,3,4],[3,4],[4]]
Prelude> window 4 6
[[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4],[1,2,3,4],[2,3,4],[3,4],[4]]
Prelude> window 6 4
[[1],[1,2],[1,2,3],[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6],[5,6],[6]]

计算 [1..4] 和 [1..5] 的卷积是这样的：

Prelude> let a = window 4 5
Prelude> let b = window 5 4
Prelude> map sum $ zipWith (zipWith (*)) a (map reverse b)
[1,4,10,20,30,34,31,20]

Answer 1

所以你想要一个 window 的长度 k 滑过给定的序列（它的长度 n 那么并不重要).

它从序列的 head 上方的最后一个单元格开始，然后逐个凹口移动，直到覆盖序列的 last 元素由它的头单元格。

这只是 map (take k) (tails sequence)，前面有 take k (inits sequence)：

window :: Int -> [a] -> [[a]]
window k  =  (++) <$> take k . inits <*> map (take k) . tails

观察：

> window 4 [1..6]
[[],[1],[1,2],[1,2,3],[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6],[5,6],[6],[]]

> window 6 [1..4]
[[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4],[2,3,4],[3,4],[4],[]]

您可以通过 init . tail 处理 []。

在 k > n 的情况下，与您想要的输出不一致。如果这很重要，则应在两部分之间插入一个额外的 xs 序列。因此我们得到

-- NB: will diverge on infinite lists
window :: Int -> [a] -> [[a]]
window k xs
   = (init . tail) $ 
     take k (inits xs)
     ++ replicate (k-n-1) xs
     ++ map (take k) (tails xs)
   where 
   n = length xs

注意：测量length是一种反模式；它在这里仅用于原型制作目的。因此，该函数将卡在无限列表中。相反，length 应该被融合进去，这样函数才会有效，立即无限期地产生连续的 windows。

所以现在我们得到

> window 4 [1..6]
[[1],[1,2],[1,2,3],[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6],[5,6],[6]]

> window 6 [1..4]
[[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4],[1,2,3,4],[2,3,4],[3,4],[4]]

tails 是线性的，而 inits 通常是二次方的，上限是 take k，所以在 k << n 的情况下它也是线性的。

为了完整起见，这里有一个不测量输入列表 length 的版本，因此它也适用于无限输入：

window :: Int -> [a] -> [[a]]
window k xs | k > 0
   = a
     ++ replicate (k - length a) xs
     ++ (init . map (take k) . tails 
              . drop 1 $ xs)
   where
   a = take k . tail $ inits xs

一种滑动window

A kind of sliding window

haskell

sliding-window