我有一个应用程序,在其中使用向量作为代码的一部分是有效的。然而,在计算过程中我需要跟踪一些元素。我听说你可以从 Data.Vectors 获得 O(n) 摊销串联(通过通常的数组增长技巧),但我认为我做得不对。假设我们有以下设置:
import Data.Vector((++),Vector)
import Prelude hiding ((++))
import Control.Monad.State.Strict
data App = S (Vector Int)
add :: Vector Int -> State App ()
add v1 = modify (\S v2 -> S (v2 ++ v1))
Does add
在这种情况下,运行时间是摊销 O(n) 吗?如果没有,我该如何制作add
这样做(我需要存储一个(forall s. MVector s Int)
在该州?)。有没有更有效的实施方式add
?
我也不太了解矢量库,所以我必须主要遵循一般原则。对它进行基准测试,运行一系列与您在应用程序中期望的类似的添加,并查看您获得的性能。如果它“足够好”,那就太好了,坚持使用简单的代码。如果没有,在存储之前(forall s. MVector s Int)
在状态下(你不能直接,元组不能容纳所有类型,所以你需要包装它),尝试通过转换为可变向量来改进添加行为,并在冻结之前执行连接以获取又是一个不可变的向量,粗略地
add v1 = do
S v2 <- get
let v3 = runST $ do
m1 <- unsafeThaw v2
m2 <- unsafeGrow m1 (length v1)
-- copy contents of v1 behind contents of v2
unsafeFreeze m2
put (S v3)
您可能需要在那里插入一些严格性。但是,如果 unsafeGrow 需要复制,则不能保证摊销 O(n) 行为。
您可以通过以下方式获得摊销 O(n) 行为
- 也将已使用的槽数存储在状态中
- 如果新向量适合末尾的自由空间,则解冻、复制、冻结而不增长
- 如果它不适合可用空间,则至少增长 2 倍,这保证每个元素平均最多被复制两次
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)