haskell - Data.Vector.dropWhile 的有效替代方案

Question

考虑以下因素:

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)

简单地获取第一个和最后一个元素并将它们相除的平均执行时间约为 27 纳秒。删除前 9 个元素并执行相同的操作平均会慢 85 毫秒或慢 3000 倍。

使用未装箱向量可将 f1 的性能提高一半以上，但我需要支持没有“Unboxed”类实例的元素。

根据dropWhile documentation它的复杂度为 O(n) 但不进行复制。 Haskell 库中是否有一种数据结构支持高效的 dropWhile 类型操作以及对第一个和最后一个元素的 O(1) 访问？

Answer 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)