我发现 Haskell Data.Vector.*
错过 C++ std::vector::push_back
的功能。有grow
/unsafeGrow
,但它们似乎具有 O(n) 复杂度。
有没有办法在一个元素的 O(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)
抬头。 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
)。
关于Haskell 向量 C++ push_back 类比,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31598273/