考虑以下:
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]
]
使用
--make -O2
编译并运行可获得以下结果: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)
仅取第一个和最后一个元素并将它们除以的平均执行时间为〜27ns。删除前9个元素并执行相同的操作的平均速度为〜85ms或慢3000倍。
使用拆箱矢量可以将
f1
的性能提高一半以上,但是我需要支持没有“拆箱”类实例的元素。根据dropWhile documentation,它的复杂度为O(n),但不进行复制。 Haskell库中是否有数据结构支持有效的dropWhile类型操作以及对第一个和最后一个元素的O(1)访问?
最佳答案
Vector
的dropWhile
出问题了。我认为最有可能的是,流融合无法正确启动,而我们为昂贵的流/捆绑构建支付了费用。可能需要进一步调查。
作为权宜之计,您可以实现自定义dropWhile
。我将您的基准测试与以下代码结合使用:
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
并得到以下结果:
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)
关于haskell - Data.Vector.dropWhile的高效替代方案,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/35419908/