haskell - 如何确保从Data.Vector摊销O(n)串联？

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

最佳答案

我也不太了解 vector 库，因此我必须主要遵循一般原则。对它进行基准测试，运行一系列类似于您在应用程序中期望的添加操作，并查看所获得的性能。如果足够好，那就坚持简单的代码。如果不是，请在状态下存储(forall s. MVector s Int)(您不能直接将其存储为元组，不能容纳forall-types，因此您需要将其包装)，请尝试通过转换为可变 vector 来改善添加行为并执行冻结之前在那里的级联，再次获得不可变的 vector

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

也存储状态中已使用的插槽数

如果新 vector 最终适合自由空间，则解冻，复制，冻结而不增加

(如果它不适合自由空间)，至少增长2倍，以确保每个元素平均被复制最多两次

关于haskell - 如何确保从Data.Vector摊销O(n)串联？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7913934/