在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，並且你將它列在基本m-n次的列表中。看起來它可能比這更有效率，但是我對如何使它更加線性化不知所措。任何接受者？

Answer 1

如果你想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) 

對話從向量列表可能會咬你一些，我不會冒險樂觀的猜測，但我會打賭，表現比單純的版本更好。

Answer 2

您可以使用Seq從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 3

首先，讓我們獲得Windows結尾沒有擔心短期的：

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

正如加布裏埃爾岡薩雷斯所說，時間複雜性是沒有更好的，如果你想使用整個結果。但是如果你只使用一些窗口，我們現在設法避免在你不使用的窗口上執行take和length的工作。

Answer 4

你不可能比O（m * n）更好，因爲這是輸出數據結構的大小。

但是，如果您顛倒操作順序，您可以避免檢查窗口的長度：首先創建n移位列表，然後將它們壓縮在一起。壓縮將擺脫那些沒有足夠元素自動。

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

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

荏苒列出的名單只是一個transposition，但不像transpose從Data.List它扔掉，將有小於ň元件的輸出。

現在很容易使窗口函數：取米名單，分別由1移位，只是壓縮他們：

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

作品也爲無限列表。

Answer 5

對於滑動窗口，我還使用了unboxed Vetors作爲長度，取，下降以及splitAt都是O（1）操作。

Thomas M. DuBuisson的代碼是一個n移位的窗口，不是滑動的，除非n = 1。因此a（++）缺失，但是這具有O（n + m）的成本。因此，小心，你把它放在哪裏。

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

windows :: Int -> Vector Double -> [[Int]] 
windows n = (unfoldr go) 
    where      
    go !xs | V.length xs < n = Nothing 
      | otherwise = 
      let (a,b) = V.splitAt 1 xs 
        c= (V.toList a ++V.toList (V.take (n-1) b)) 
      in (c,b) 

我嘗試過了與+RTS -sstderr和：

putStrLn $ show (L.sum $ L.concat $ windows 10 (U.fromList $ [1..1000000])) 

，並得到實時1.051s和96.9％的使用率，同時要注意的是，滑窗後進行兩個O（M）操作。