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 .这有以下缺点

任何操作这种数据结构的代码最终都必须是一元的

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

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

好像这一切还不够，垃圾收集在纯代码中也表现得更好。

那我该怎么办？

您并不经常需要这种行为 - 通常您最好使用不可变的数据结构(从而避免所有上述问题)，它会做类似的事情。仅限于 containers GHC 附带的一些替代方案包括:

如果您几乎总是只使用 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是一元操作。

虽然这不是拆箱，但复制 vector 不会太困难小号 data family approach - 这只是乏味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 issue在解释语义方面做得很好:

I think the intended semantics are that it may do a realloc, but not guaranteed to, and all the current implementations do the simpler copying semantics because for on heap allocations the cost should be roughly the same.

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

1 方法是，对于您想要拥有的每种新类型的未装箱矢量，您制作一个 data instance将您的类型“扩展”为固定数量的未装箱数组(或其他未装箱向量)。这是 data family 的重点- 允许一个类型的不同实例具有完全不同的运行时表示，并且也是可扩展的(如果需要，您可以添加自己的 data instance)。