haskell - Haskell向量C++ push_back模拟

我发现Haskell Data.Vector.*缺少C++ std::vector::push_back的功能。有grow / unsafeGrow，但它们似乎具有O(n)复杂度。

有没有一种方法可以在元素的O(1)摊销时间内增长 vector ？

最佳答案

没有，Data.Vector中确实没有这样的功能。像MutableArray一样，使用 Data.Vector.Mutable 从头开始实现它并不难(请参阅下面的实现)，但是存在一些明显的缺点。特别是，它的所有操作最终都发生在某些状态上下文内，通常是ST或IO。缺点是

任何操纵这种数据结构的代码最终都必须是monadic

编译器最不可能进行优化。例如，像vector这样的库使用了一种非常聪明的东西fusion来优化中间分配。在状态上下文中，这种事情是不可能的。

并行性将变得更加困难:在ST中，我什至没有两个线程，在IO中，我将在所有地方都具有竞争条件。这里令人讨厌的一点是，任何共享都必须在IO中进行。

似乎还不够，垃圾收集在纯代码中的性能也更好。

那我该怎么办？

通常不需要这种行为-通常，最好使用做类似事情的不可变数据结构(从而避免所有上述问题)。仅将自己限制在GHC随附的 containers 中，一些替代方法包括:

如果您几乎总是只使用push_back，也许您只想要一个堆栈(一个普通的旧[a])。

(如果您期望做的push_back比查找更多)， Data.Sequence 会给您O(1)附加到末尾并添加O(log n)查找。

如果您对很多操作(尤其是类似哈希图的操作)感兴趣，那么 Data.IntMap 进行了优化。即使这些操作的理论成本是O(log n)，您也将需要相当大的IntMap才能开始感受到这些成本。

制作类似C++的vector
当然，如果不关心最初提到的限制，则没有理由不使用类似C++的 vector 。只是为了好玩，我才从头开始实现(需要打包data-default和primitive)。

该代码可能尚未在某些库中存在的原因是，它与Haskell的许多精神背道而驰(我这样做的目的是为了遵循C++样式 vector )。

唯一实际产生新 vector 的操作是newVector-其他所有操作都会“修改”现有 vector 。由于pushBack不返回新的GrowVector，因此必须修改现有的length(包括其长度和/或容量)，因此capacity和length必须是“指针”。反过来，这意味着即使获得vector也是单子(monad)操作。

虽然未取消装箱，但要复制data family的 grow approach并不难，因为这很乏味。

照这样说:

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 issue很好地解释了语义:

我认为预期的语义是它可以进行重新分配，但不能保证这样做，并且当前的所有实现都采用更简单的复制语义，因为对于堆分配，成本应该大致相同。

基本上，当您想要一个新的可变大小的可变 vector (从旧 vector 的元素开始(不再关心旧 vector ))时，应该使用GrowVector。这非常有用-例如，可以使用MVector和grow实现data instance。

1这种方法是，对于每种想要的新型非盒装 vector ，都需要创建一个data family，将您的类型“扩展”为固定数量的非盒装数组(或其他非盒装 vector )。这就是data instance的重点-允许类型的不同实例具有完全不同的运行时表示形式，并且还可以扩展(如果需要，可以添加自己的ojit_code)。

关于haskell - Haskell向量C++ push_back模拟，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31598273/