einen effizienten Sliding-Window-Algorithmus in Haskell

Question

Implementierung brauchte ich eine effiziente Fensterfunktion in Haskell Schiebe-, also schrieb ich folgend:

windows n xz@(x:xs) 
    | length v < n = [] 
    | otherwise = v : windows n xs 
    where 
    v = take n xz 

Mein Problem dabei ist, dass ich denke, die Komplexität ist O (n * m) wobei m die Länge der Liste und n die Fenstergröße ist. Sie zählen die Liste einmal für take, ein anderes Mal für length, und Sie tun es unten die Liste von im Wesentlichen m-n Zeiten. Es scheint, als könnte es effizienter sein, aber ich weiß nicht, wie ich es linearer machen soll. Irgendwelche Abnehmer?

Answer 1

Wenn Sie O (1) Länge wollen, warum nicht eine Struktur verwenden, die O (1) Länge bietet? Angenommen, Sie sind nicht für die Fenster aus einer unendlichen Liste suchen, in Betracht ziehen:

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) 

Conversation jedes Fensters von einem Vektor zu einer Liste können Sie einige beißen, ich will nicht, dass es eine optimistische Vermutung Gefahr, aber ich Ich wette, dass die Leistung besser ist als die reine Listenversion.

Answer 2

Sie können Seq von Data.Sequence verwenden, die O (1) enqueue und dequeue an beiden Enden hat:

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 _ _ [] = [] 

Beachten Sie, wenn Sie das gesamte Ergebnis Ihres Algorithmus materialisieren notwendigerweise O (N * M) seit Das ist die Größe Ihres Ergebnisses. Die Verwendung von Seq verbessert nur die Leistung um einen konstanten Faktor.

Beispiel für die Verwendung:

>>> windows [1..5] 
[[1,2,3],[2,3,4],[3,4,5]] 

Answer 3

Lassen Sie uns zunächst die Fenster erhalten, ohne am Ende über die kurzen besorgniserregend:

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

Jetzt wollen wir von den Kurzen loszuwerden, ohne die Länge Überprüfung Von allen.

Da wir wissen, dass sie am Ende sind, könnten wir sie so verlieren:

windows n xs = take (length xs - n + 1) (windows' n xs) 

Aber das ist nicht groß, da wir durch xs eine zusätzliche Zeit gehen noch seine Länge zu erhalten. Es funktioniert auch nicht auf unendlichen Listen, die Ihre ursprüngliche Lösung getan hat.

Stattdessen lassen Sie uns für die Verwendung einer Liste als Lineal eine Funktion schreiben, um die Menge zu messen, von anderen zu nehmen:

takeLengthOf :: [a] -> [b] -> [b] 
takeLengthOf = zipWith (flip const) 

> takeLengthOf ["elements", "get", "ignored"] [1..10] 
[1,2,3] 

Jetzt haben wir dieses schreiben kann:

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

Arbeiten auf unendliche Listen zu :

> take 5 (windows 3 [1..]) 
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7]] 

Wie Gabriel Gonzalez sagt, ist die Zeit Komplexität nicht besser, wenn Sie wollen benutze das ganze Ergebnis. Aber wenn Sie nur einige der Fenster verwenden, schaffen wir es jetzt, die Arbeit von take und length auf denen zu vermeiden, die Sie nicht verwenden.

Answer 4

Sie können nicht besser als O (m * n), da dies die Größe der Ausgabedatenstruktur ist.

Aber Sie können vermeiden, die Länge der Fenster zu überprüfen, wenn Sie die Reihenfolge der Vorgänge umkehren: Erstellen Sie zuerst n verschobenen Listen und dann nur zusammen zippen. Zipping wird diejenigen loswerden, die nicht genug Elemente automatisch haben.

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

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

eine Liste von Listen Zipping ist nur ein transposition, aber im Gegensatz zu transpose aus Data.List es wegwirft Ausgänge, die weniger als n Elemente haben würde.

Jetzt ist es einfach, die Fensterfunktion zu machen: Nehmen Sie m Listen, die jeweils um 1 verschoben und zip sie nur:

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

Arbeiten auch für unendliche Listen.

Answer 5

für das Schiebefenster I verwendet auch unboxed Vetors wie Länge, nehmen, fallen sowie splitAt sind O (1) Operationen.

Der Code von Thomas M. Dubuisson ist ein Fenster von n verschoben ist, kein Gleiten, außer wenn n = 1 ist. Daher ist ein (++) fehlt, jedoch hat dies einen Kosten für O (n + m). Also vorsichtig, wo du es hingestellt hast.

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) 

ich es ausprobiert mit +RTS -sstderr und:

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

und bekam Echtzeit 1.051s und 96,9% Verwendung, dass nach dem Schiebefenster zwei O (m) unter Berücksichtigung Operationen ausgeführt werden.