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?
'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
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
Penso che sarebbe utile presentare un bug report – jberryman