如何优化Haskell中支持窗口长度大于序列长度的滑动窗口实现

优化实现方案 #

存在线性时间复杂度的更优实现，核心思路是根据滑动窗口的生成规律拆分三个阶段单独处理，避免每次都对原始序列重复执行take/drop操作：

import Data.List (tails)

window :: Int -> Int -> [[Int]]
window n k = growPhase ++ stablePhase ++ shrinkPhase
  where
    fullSeq = [1..n]
    minVal = min n k
    -- 增长阶段：窗口长度从1逐步增加到min(n,k)
    growPhase = [take i fullSeq | i <- [1..minVal]]
    -- 平稳阶段：如果窗口长度k大于序列长度n，重复输出完整序列k-n次
    stablePhase = replicate (max 0 (k - n)) fullSeq
    -- 收缩阶段：每次移除窗口首元素，直到窗口只剩最后一个元素
    shrinkPhase = drop 1 $ init $ tails fullSeq

如果需要兼容任意内容的输入序列（不限于[1..n]），可以改成通用版本：

import Data.List (tails)

genericWindow :: Int -> [a] -> [[a]]
genericWindow k xs = growPhase ++ stablePhase ++ shrinkPhase
  where
    n = length xs
    minVal = min n k
    growPhase = [take i xs | i <- [1..minVal]]
    stablePhase = replicate (max 0 (k - n)) xs
    shrinkPhase = drop 1 $ init $ tails xs

实现说明 #

1. 原实现的时间复杂度为O((n+k)*min(n,k))，属于平方级，原因是每次生成窗口都需要从原始序列的头部重新计算前缀、删除前缀，没有复用之前的计算结果。
2. 优化后的实现总时间复杂度为O(n+k)，属于线性级：
   • 增长阶段仅执行min(n,k)次前缀截取，没有重复计算
   • 平稳阶段利用Haskell列表的惰性共享特性，重复输出同一个序列不会产生额外复制开销
   • 收缩阶段直接调用标准库tails函数，一次遍历即可生成所有后缀窗口

效果验证 #

该实现输出结果和原实现完全一致：

-- 测试用例1
> window 4 4
[[1],[1,2],[1,2,3],[1,2,3,4],[2,3,4],[3,4],[4]]
-- 测试用例2
> 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]]
-- 测试用例3
> 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]]
-- 卷积计算测试
> let a = genericWindow 5 [1..4]
> let b = genericWindow 4 [1..5]
> map sum $ zipWith (zipWith (*)) a (map reverse b)
[1,4,10,20,30,34,31,20]

内容的提问来源于stack exchange，提问作者Theo H