我发现 HaskellData.Vector.*错过了 C++std::vector::push_back的功能。有grow/ unsafeGrow，但它们似乎具有O(n)复杂性。
有没有办法在一个元素的O(1)摊销时间内增长向量？
问问题
804 次
1 回答
14
不，真的没有这样的设施Data.Vector。MutableArray使用like do 从头开始实现这一点并不难Data.Vector.Mutable（见下面我的实现），但有一些明显的缺点。特别是，它的所有操作最终都发生在某个状态上下文中，通常是ST或IO。这有以下缺点
- 任何操纵这种数据结构的代码最终都必须是单子的
- 编译器不太可能进行优化。例如，库之类的
vector使用非常聪明的东西叫做融合来优化中间分配。这种事情在状态上下文中是不可能的。 - 并行性将变得更加困难：
ST我什至不能有两个线程，而且IO我将到处都有竞争条件。这里令人讨厌的一点是，任何共享都必须在IO.
好像这一切还不够，垃圾收集在纯代码中也表现得更好。
那我该怎么办？
你并不经常需要这种行为——通常你最好使用不可变的数据结构（从而避免所有上述问题），它做类似的事情。仅将自己限制在containersGHC 附带的范围内，一些替代方案包括：
- 如果您几乎总是只使用
push_back，也许您只想要一个堆栈（一个普通的旧[a]）。 - 如果您预计要做的
push_back不仅仅是查找，Data.Sequence则可以O(1)附加到任一端和O(log n)查找。 - 如果您对很多操作感兴趣，尤其是类似 hashmap 的操作，那么
Data.IntMap它是非常优化的。即使这些操作的理论成本是O(log n)，您也需要相当大IntMap的成本才能开始感受这些成本。
制作类似 C++ 的东西vector
当然，如果一个人不关心最初提到的限制，那么没有理由不拥有类似 C++ 的向量。只是为了好玩，我继续从头开始实现这个（需要包data-default和primitive）。
这段代码可能不在某些库中的原因是它违背了 Haskell 的大部分精神（我这样做是为了符合 C++ 样式向量）。
- 唯一实际创建新向量的操作是
newVector- 其他所有操作都会“修改”现有向量。由于pushBack不返回一个新的GrowVector，它必须修改现有的（包括它的长度和/或容量），所以length必须capacity是“指针”。反过来，这意味着即使得到 thelength也是一个单子操作。 vector虽然这不是开箱即用的，但复制sdata family方法并不会太难——这只是乏味1。
照这样说：
module GrowVector (
GrowVector, newEmpty, size, read, write, pushBack, popBack
) where
import Data.Primitive.Array
import Data.Primitive.MutVar
import Data.Default
import Control.Monad
import Control.Monad.Primitive (PrimState, PrimMonad)
import Prelude hiding (length, read)
data GrowVector s a = GrowVector
{ underlying :: MutVar s (MutableArray s a) -- ^ underlying array
, length :: MutVar s Int -- ^ perceived length of vector
, capacity :: MutVar s Int -- ^ actual capacity
}
type GrowVectorIO = GrowVector (PrimState IO)
-- | Make a new empty vector with the given capacity. O(n)
newEmpty :: (Default a, PrimMonad m) => Int -> m (GrowVector (PrimState m) a)
newEmpty cap = do
arr <- newArray cap def
GrowVector <$> newMutVar arr <*> newMutVar 0 <*> newMutVar cap
-- | Read an element in the vector (unchecked). O(1)
read :: PrimMonad m => GrowVector (PrimState m) a -> Int -> m a
g `read` i = do arr <- readMutVar (underlying g); arr `readArray` i
-- | Find the size of the vector. O(1)
size :: PrimMonad m => GrowVector (PrimState m) a -> m Int
size g = readMutVar (length g)
-- | Double the vector capacity. O(n)
resize :: (Default a, PrimMonad m) => GrowVector (PrimState m) a -> m ()
resize g = do
curCap <- readMutVar (capacity g) -- read current capacity
curArr <- readMutVar (underlying g) -- read current array
curLen <- readMutVar (length g) -- read current length
newArr <- newArray (2 * curCap) def -- allocate a new array twice as big
copyMutableArray newArr 1 curArr 1 curLen -- copy the old array over
underlying g `writeMutVar` newArr -- use the new array in the vector
capacity g `modifyMutVar'` (*2) -- update the capacity in the vector
-- | Write an element to the array (unchecked). O(1)
write :: PrimMonad m => GrowVector (PrimState m) a -> Int -> a -> m ()
write g i x = do arr <- readMutVar (underlying g); writeArray arr i x
-- | Pop an element of the vector, mutating it (unchecked). O(1)
popBack :: PrimMonad m => GrowVector (PrimState m) a -> m a
popBack g = do
s <- size g;
x <- g `read` (s - 1)
length g `modifyMutVar'` (+ negate 1)
pure x
-- | Push an element. (Amortized) O(1)
pushBack :: (Default a, PrimMonad m) => GrowVector (PrimState m) a -> a -> m ()
pushBack g x = do
s <- readMutVar (length g) -- read current size
c <- readMutVar (capacity g) -- read current capacity
when (s+1 == c) (resize g) -- if need be, resize
write g (s+1) x -- write to the back of the array
length g `modifyMutVar'` (+1) -- increase te length
当前的语义grow
我认为github 问题在解释语义方面做得很好：
我认为预期的语义是它可能会执行重新分配，但不能保证这样做，并且所有当前的实现都执行更简单的复制语义，因为对于堆分配，成本应该大致相同。
基本上，grow当您想要一个增加大小的新可变向量时，您应该使用，从旧向量的元素开始（不再关心旧向量）。这是非常有用的——例如可以GrowVector使用MVectorand来实现grow。
1方法是，对于您想要拥有的每种新类型的未装箱矢量，您都data instance将您的类型“扩展”为固定数量的未装箱数组（或其他未装箱矢量）。这就是data family- 允许类型的不同实例具有完全不同的运行时表示，并且也是可扩展的（data instance如果需要，您可以添加自己的）。
于 2016-11-19T21:43:36.840 回答