2016-02-15 22 views
7

Si consideri il seguente:efficiente alternativa al Data.Vector.dropWhile

module Main where 

import   Criterion.Main 
import qualified Data.Vector as V 

f1 :: V.Vector Double -> Double 
f1 xs 
    | V.null xs = 0 
    | otherwise = V.last xss/V.head xss 
    where xss = V.dropWhile (< 10) xs 

f2 :: V.Vector Double -> Double 
f2 xs 
    | V.null xs = 0 
    | otherwise = V.last xs/V.head xs 

setupEnv :: IO (V.Vector Double) 
setupEnv = return $ V.enumFromN 0 10000000 

main :: IO() 
main = defaultMain [ 
    env setupEnv $ \v -> 
    bgroup "funcs" [bench "f1" $ nf f1 v , bench "f2" $ nf f2 v] 
    ] 

Compilare con --make -O2 e funzionante dà il seguente risultato:

app $ ./A 
benchmarking funcs/f1 
time     81.87 ms (78.34 ms .. 86.06 ms) 
        0.998 R² (0.996 R² .. 1.000 R²) 
mean     85.87 ms (84.16 ms .. 87.13 ms) 
std dev    2.351 ms (1.169 ms .. 3.115 ms) 

benchmarking funcs/f2 
time     27.50 ns (27.11 ns .. 27.95 ns) 
        0.998 R² (0.996 R² .. 0.999 R²) 
mean     27.62 ns (27.21 ns .. 28.05 ns) 
std dev    1.391 ns (1.154 ns .. 1.744 ns) 
variance introduced by outliers: 73% (severely inflated) 

Il tempo di esecuzione della media semplicemente prendendo il primo e l'ultimo elementi e dividendoli è ~ 27ns. Eliminare i primi 9 elementi e eseguire la stessa operazione ha una media di ~ 85 ms o 3000x più lento.

L'utilizzo di un vettore unbox migliora le prestazioni di f1 di oltre la metà, tuttavia è necessario supportare elementi che non presentano istanze della classe "Unboxed".

In base allo dropWhile documentation ha una complessità di O (n) ma non copia. Esiste una struttura dati nelle librerie Haskell che supporta un'efficiente operazione dropWhile-type e l'accesso O (1) al primo e all'ultimo elemento?

+1

'f1' non dovrebbe essere così lento; questo dovrebbe essere un semplice traversamento di (in questo caso) 10 elementi e quindi una regolazione dell'indice e dell'offset nel 'Vector'. 'dropWhile' alla fine sembra essere implementato con questo flusso fusion che presumo non si deve comportare bene http://hackage.haskell.org/package/vector-0.11.0.0/docs/src/Data-Vector-Fusion-Stream -Monadic.html # dropWhileM – jberryman

+0

la struttura dati che mi viene in mente è 'Seq a' da' Data.Sequence', che potrebbe essere adatta al tuo problema se prevale il problema 'vector'. – epsilonhalbe

+3

Penso che sarebbe utile presentare un bug report – jberryman

risposta

4

C'è qualcosa che non va condropWhile. Penso che sia più probabile che la fusione del flusso non riesca a dare il via giusta e paghiamo per la costosa costruzione di stream/bundle. Qualche ulteriore indagine è probabilmente dovuta.

Come misura di interruzione, è possibile implementare un numero personalizzato dropWhile. Ho usato il vostro punto di riferimento con il seguente codice:

dropWhile' :: (a -> Bool) -> V.Vector a -> V.Vector a 
dropWhile' p v = V.drop (go 0) v where 
    go n | n == V.length v  = n 
     | p (V.unsafeIndex v n) = go (n + 1) 
     | otherwise    = n 

e ottenuto i seguenti risultati:

benchmarking funcs/f1 
time     57.70 ns (56.35 ns .. 59.46 ns) 

benchmarking funcs/f2 
time     19.68 ns (19.44 ns .. 19.91 ns) 
+1

Grazie! Ho presentato un problema a questo proposito: https://github.com/haskell/vector/issues/108 –

+0

Grazie per il vostro impegno. –

+0

ho commentato il biglietto con alcune ipotesi che dovrebbero permettere di scavare in questa domanda :) –