我如何确保从Data.Vector中并发O（n）级联？ [英] How can I ensure amortized O(n) concatenation from Data.Vector?

问题描述

我有一个应用程序，可以将代码的一部分使用向量。但是，在计算过程中，我需要跟踪一些元素。我听说你可以从Data.Vectors获得O（n）分期连接（按照通常的数组增长技巧），但我认为我做得不对。因此，可以说我们有以下设置：

$ $ p $ 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））

在这种情况下，是否在分摊的O（n）时间内运行 add ？如果不是，我该如何使 add 做到这一点（是否需要存储（所有s。MVector s Int）在国家？）。有没有更高效的方法来实现 add ？

解决方案

我也不知道矢量库，所以我必须坚持一般原则。对它进行基准测试，运行一系列类似于您在应用程序中预期的添加，并查看您获得的性能。如果它够好，那么很好，坚持简单的代码。如果不存在，那么在存储（forall s。MVector s Int）状态之前（不能直接存储元组不能保存全部类型， d需要包装它），尝试通过转换为可变向量来改善添加行为，并在冻结前执行连接以再次获得不可变向量，大致如下：

pre > add v1 = do
S v2 < - get
let v3 = runST $ do
m1 < - unsafeThaw v2
m2 < - unsafeGrow m1（长度v1）
- 复制v1内容后的内容
unsafeFreeze m2
put（S v3）


您可能需要在其中插入一些严格的内容。但是，如果unsafeGrow需要复制，则不能保证O（n）行为的摊销。

您可以通过$ b获得摊销O（n）行为
$ b

1. 如果新的矢量在最后的空闲空间中适合，则也在该状态下存储已使用的槽的数量
   
2. 解冻，复制，冻结而不增长
   
3. 如果它不适合可用空间，则增长至少2倍，保证每个元素最多可复制两次

I have an application where it is efficient to use Vectors for one part of the code. However, during the computation I need to keep track of some of the elements. I have heard that you can get O(n) amortized concatenation from Data.Vectors (by the usual array growing trick) but I think that I am not doing it right. So lets say we have the following setup:

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 run in amortized O(n) time in this case? If not, how can I make add do that (do I need to store an (forall s. MVector s Int) in the State?). Is there a more efficient way of implementing add?

解决方案

I don't know the vector library well either, so I have to stick to general principles mostly. Benchmark it, run a sequence of adds similar to what you expect in your application and see what performance you get. If it's 'good enough', great, stick with the simple code. If not, before storing a (forall s. MVector s Int) in the state (which you can't directly, tuples can't hold forall-types, so you'd need to wrap it), try improving the add-behaviour by converting to mutable vectors and perform the concatenation there before freezing to get an immutable vector again, roughly

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)

You may need to insert some strictness there. However, if unsafeGrow needs to copy, that will not guarantee amortized O(n) behaviour.

You can get amortized O(n) behaviour by

1. storing the number of used slots in the state too
2. if the new vector fits in the free space at the end, thaw, copy, freeze without growing
3. if it doesn't fit in the free space, grow by at least a factor of 2, that guarantees that each element is copied at most twice on average

这篇关于我如何确保从Data.Vector中并发O（n）级联？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！