Skuteczna alternatywa dla Data.Vector.dropWhile

Question

Rozważmy następujący:

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

Kompilacja z --make -O2 i prowadzenie daje następujący wynik:

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) 

Średni czas wykonania po prostu sobą pierwszy i ostatni elementy i ich podział to ~ 27ns. Upuszczenie pierwszych 9 elementów i wykonanie tej samej operacji ma średnio ~ 85ms lub 3000x mniej.

Używanie rozpakowanego wektora zwiększa wydajność o f1 o ponad połowę, ale muszę obsługiwać elementy, które nie mają instancji klasy "Unboxed".

Zgodnie z dropWhile documentation ma on złożoność O (n), ale nie kopiuje. Czy istnieje struktura danych w bibliotekach Haskell, która obsługuje wydajną operację typu dropWhile i O (1) dostęp do pierwszego i ostatniego elementu?

Answer 1

Coś jest nie tak z Vector 's dropWhile. Sądzę, że najprawdopodobniej fuzja strumieniowa nie powiedzie się poprawnie i zapłacimy za kosztowny strumień/pakiet. Pewne dalsze dochodzenie jest prawdopodobnie spowodowane.

Jako miarę tymczasową można wdrożyć niestandardową dropWhile. Kiedyś swoje odniesienia z następującego kodu:

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 

i otrzymał następujące wyniki:

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)