Haskell向量C++ push_back模拟

Question

我发现Haskell Data.Vector.*错过了C++ std::vector::push_back的功能.有grow/ unsafeGrow,但它们似乎有O(n)复杂性.

有没有办法在O(1)元素的摊销时间内增长向量？

Answer 1

不,确实没有这样的设施Data.Vector.使用MutableArray类似的方法从头开始实现这一点并不太难Data.Vector.Mutable(参见下面的实现),但是存在一些明显的缺点.特别是,其所有操作结束了一些状态上下文中通常发生ST或IO.这有缺点

1. 任何操纵这种数据结构的代码最终都必须是monadic
2. 编译器不太可能进行优化.例如,库就像vector使用一些非常聪明的东西,称为融合来优化中间分配.在州情境中,这种事情是不可能的.
3. 并行性将变得更加困难: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必须是"指针".反过来,这意味着即使获得这length是一个monadic操作.
• 虽然这不是拆箱,它不会是太难以复制vector小号data family的方法 -它只是乏味¹.

照这样说:

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问题在解释语义方面做得很好:

我认为预期的语义是它可以执行realloc,但不能保证,并且所有当前实现都执行更简单的复制语义,因为对于堆分配,成本应该大致相同.

基本上你应该使用grow当你想要一个增加大小的新的可变向量时,从旧向量的元素开始(并且不再关心旧向量).这非常有用 - 例如,可以实现GrowVector使用MVector和grow.

¹方法是,对于您想要的每种新类型的未装箱矢量,您可以data instance将您的类型"扩展"为固定数量的未装箱数组(或其他未装箱的矢量).这是data family- 允许类型的不同实例化具有完全不同的运行时表示,并且也可以是可扩展的(data instance如果需要,可以添加自己的实例).