haskell – Data.Vector.dropWhile的有效替代品

发布时间：2020-12-15 00:54:56 所属栏目：Java 来源：网络整理

导读：考虑以下： module Main whereimport Criterion.Mainimport qualified Data.Vector as Vf1 :: V.Vector Double - Doublef1 xs | V.null xs = 0 | otherwise = V.last xss / V.head xss where xss = V.dropWhile ( 10) xsf2 :: V.Vector Double - Doublef2 xs

考虑以下：

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 R2   (0.996 R2 .. 1.000 R2)
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 R2   (0.996 R2 .. 0.999 R2)
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个元素并执行相同操作的平均值约为85毫秒或慢3000倍.

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

根据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)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!