Haskell векторный C++ push_back аналог

Question

Я обнаружил, что Хаскелл Data.Vector.* скучаю по С ++ std::vector::push_backфункциональность. Есть grow/unsafeGrow, но они, кажется, имеют сложность O(n).

Есть ли способ вырастить векторы за O(1) амортизированного времени для элемента?

Answer 1

Нет, на самом деле нет такой возможности в Data.Vector, Это не так сложно реализовать с нуля, используя MutableArray лайк Data.Vector.Mutable делает (см. мою реализацию ниже), но есть некоторые существенные недостатки. В частности, все его операции в конечном итоге происходят внутри некоторого контекста состояния, обычно ST или же IO, Это имеет недостатки, которые

1. Любой код, который манипулирует такой структурой данных, в конечном итоге должен быть монадическим
2. Компилятор с меньшей вероятностью сможет оптимизировать. Например, библиотеки типа vector используйте что-то действительно умное, называемое fusion, чтобы оптимизировать промежуточные распределения. Подобные вещи невозможны в государственном контексте.
3. Параллелизм будет намного сложнее: в 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 s 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 довольно хорошо объясняет семантику:

Я думаю, что предполагаемая семантика состоит в том, что она может выполнять реаллок, но не гарантируется, и все текущие реализации делают более простую семантику копирования, потому что для распределений в куче стоимость должна быть примерно одинаковой.

В основном вы должны использовать grow когда вам нужен новый изменяемый вектор увеличенного размера, начиная с элементов старого вектора (и больше не заботится о старом векторе). Это очень полезно - например, можно реализовать GrowVector с помощью MVector а также grow,

---

¹ подход заключается в том, что для каждого нового типа неупакованного вектора, который вы хотите иметь, вы делаете data instance это "расширяет" ваш тип в фиксированное количество неупакованных массивов (или других неупакованных векторов). Это точка data family - разрешить различным экземплярам типа иметь абсолютно разные представления времени выполнения, а также быть расширяемым (вы можете добавить свой собственный data instance если ты хочешь).