3

我有一个应用程序，可以有效地将向量用于代码的一部分。但是，在计算过程中，我需要跟踪一些元素。我听说您可以从 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))

在这种情况下是否add在摊销的 O(n) 时间内运行？如果没有，我该怎么add做（我需要(forall s. MVector s Int)在州内存储一个吗？）。有没有更有效的实施方式add？

4

1 回答 1

2

我也不太了解向量库，所以我主要还是要坚持一般原则。对其进行基准测试，运行一系列与您在应用程序中所期望的类似的添加，并查看您获得的性能。如果它“足够好”，那就太好了，坚持使用简单的代码。如果不是，在将 a 存储(forall s. MVector s Int)在状态之前（你不能直接，元组不能保存所有类型，所以你需要包装它），尝试通过转换为可变向量来改进 add-behaviour 并执行在冻结之前连接那里再次获得一个不可变的向量，大致

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) 行为

  1. 也存储状态中已使用插槽的数量
  2. 如果新向量最后适合空闲空间，则解冻、复制、冻结而不增长
  3. 如果它不适合可用空间，则至少增长 2 倍，这保证每个元素平均最多被复制两次
于 2011-10-27T12:43:38.057 回答