hiệu quả thay thế cho Data.Vector.dropWhile

Question

xem xét như sau:

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

Biên soạn với --make -O2 và chạy cho kết quả sau:

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) 

Giá trị trung bình thời gian thực hiện đơn giản là lấy đầu tiên và cuối cùng các yếu tố và phân chia chúng là ~ 27ns. Việc giảm 9 thành phần đầu tiên và thực hiện cùng một thao tác có nghĩa là ~ 85ms hoặc 3000x chậm hơn.

Sử dụng véc tơ không được chuyển giúp cải thiện hiệu suất của f1 hơn một nửa, nhưng tôi cần hỗ trợ các yếu tố không có trường hợp nào của lớp "Không được hộp".

Theo số dropWhile documentation nó có độ phức tạp của O (n) nhưng không sao chép. Có cấu trúc dữ liệu nào trong các thư viện Haskell hỗ trợ thao tác loại dropWhile hiệu quả và truy cập O (1) vào các phần tử đầu tiên và cuối cùng không?

Answer 1

Có điều gì đó sai với Vector 's dropWhile. Tôi nghĩ rằng có khả năng nhất là sự hợp nhất của luồng không thể đá chính xác và chúng tôi trả tiền cho việc xây dựng luồng/gói tốn kém. Một số điều tra thêm có lẽ là do.

Là biện pháp ngăn chặn, bạn có thể triển khai dropWhile tùy chỉnh. Tôi sử dụng benchmark của bạn với đoạn mã sau:

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 

Và có kết quả như sau:

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)