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

问题描述

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

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

我的问题是我认为复杂度是 O(n*m)，其中 m 是列表的长度，n 是窗口大小.你对 take 的列表倒数一次，length 再倒数一次，然后你在列表中向下倒数 m-n 次.似乎它可以比这更有效，但我不知道如何使它更线性.有吃货吗?

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?

推荐答案

没有比 O(m*n) 更好的了，因为这是输出数据结构的大小.

You can't get better than O(m*n), since this is the size of the output data structure.

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

But you can avoid checking the lengths of the windows if you reverse the order of operations: First create n shifted lists and then just zip them together. Zipping will get rid of those that don't have enough elements automatically.

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

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

压缩列表列表只是一个转置，但与transpose不同code> 来自 Data.List 它会丢弃少于 n 个元素的输出.

Zipping a list of lists is just a transposition, but unlike transpose from Data.List it throws away outputs that would have less than n elements.

现在很容易制作窗口函数:取 m 个列表，每个列表移动 1，然后压缩它们:

Now it's easy to make the window function: Take m lists, each shifted by 1, and just zip them:

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

也适用于无限列表.

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