haskell - 推拉窗的一种

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

它是长度为 k 的滑动窗口，在长度为 n 的序列上，其中 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

所以你想要一个长度为 k 的窗口在给定序列上滑动(它的长度n并不重要)。

它从序列头部上方的最后一个单元开始，然后逐个缺口移动，直到其头部覆盖序列的最后元素细胞。

这就是 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是一种反模式；它在这里仅用于原型(prototype)设计目的。因此，该函数将陷入无限列表中。相反，length应该被融合进来，这样函数就会变得高效，立即无限期地产生连续的窗口。

现在我们得到了

> 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