Implementazione di un algoritmo efficiente finestra scorrevole in Haskell

Question

avevo bisogno di una funzione finestra efficiente scorrevole in Haskell, così ho scritto il seguente:

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

Il mio problema con questo è che penso che la complessità è O (n * m) dove m è la lunghezza della lista e n è la dimensione della finestra. Un conto alla rovescia dell'elenco una volta per take, un'altra volta per length, e lo si fa in basso nell'elenco delle volte essenzialmente di m-n. Sembra che possa essere più efficiente di questo, ma non riesco a renderlo più lineare. Qualche acquirente?

Answer 1

Se si desidera la lunghezza O (1), perché non utilizzare una struttura che fornisce la lunghezza O (1)? Dando per scontato che non siete alla ricerca per le finestre da un elenco infinito, è possibile utilizzare:

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) 

Conversazione di ciascuna finestra da un vettore a un elenco potrebbe mordere un po ', non voglio azzardare un'ipotesi ottimistica lì, ma io scommetteremo che le prestazioni sono migliori rispetto alla versione solo elenco.

Answer 2

È possibile utilizzare Seq da Data.Sequence, che ha O (1) accodamento e dequeue alle due estremità:

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

Si noti che se si materializzare l'intero risultato vostro algoritmo è necessariamente O (N * M) dal questa è la dimensione del tuo risultato. L'utilizzo di Seq migliora semplicemente le prestazioni di un fattore costante.

uso Esempio:

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

Answer 3

Prima andiamo alle finestre senza preoccuparsi di quelli brevi alla fine:

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

Ora ci vogliono sbarazzarsi di quelli brevi senza controllare la lunghezza di ognuno.

Dal momento sappiamo che sono alla fine, siamo riusciti a perdere in questo modo:

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

Ma non è fantastica dato che ancora attraversiamo xs un tempo supplementare per ottenere la sua lunghezza. Inoltre, non funziona su elenchi infiniti, cosa che ha fatto la tua soluzione originale.

Invece cerchiamo di scrivere una funzione per l'utilizzo di una lista come un righello per misurare la quantità di prendere da un altro:

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

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

Ora possiamo scrivere questo:

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

Opere su infinite liste troppo :

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

Come dice Gabriel Gonzalez, la complessità del tempo non è migliore se si desidera utilizzare l'intero risultato. Ma se usi solo alcune finestre, ora riusciamo a evitare di fare il lavoro di take e di length su quelle che non usi.

Answer 4

Non è possibile ottenere risultati migliori di O (m * n), poiché questa è la dimensione della struttura dati di output.

Tuttavia, è possibile evitare di controllare la lunghezza delle finestre se si inverte l'ordine delle operazioni: creare prima gli elenchi spostati n e quindi unirli insieme. Zippare si sbarazzerà di quelli che non hanno abbastanza elementi automaticamente.

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

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

Zippare una lista di liste è solo un transposition, ma a differenza di transpose da Data.List si butta via le uscite che avrebbero meno di n elementi.

Ora è facile per rendere la funzione di finestra: Prendere m liste, ciascuna spostata di 1, e solo li zip:

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

funziona anche per le liste infinite.

Answer 5

Per la finestra scorrevole ho utilizzato anche i vetori unboxed come lunghezza, take, drop e splitAt sono operazioni O (1).

Il codice di Thomas M. DuBuisson è una finestra per n spostata, non uno scorrimento, tranne se n = 1. Quindi manca un (++), tuttavia questo ha un costo di O (n + m). Quindi attento, dove lo metti.

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) 

ho provato con +RTS -sstderr e:

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

e ottenuto in tempo reale e l'uso 1.051s 96,9%, tenendo presente che dopo la finestra scorrevole vengono eseguite due operazioni O (m).