Как я могу обеспечить амортизацию O(n) от Data.Vector?

Question

У меня есть приложение, в котором эффективно использовать Векторы для одной части кода. Однако во время вычислений мне нужно отслеживать некоторые элементы. Я слышал, что вы можете получить O(n) амортизированную конкатенацию от Data.Vectors (обычным способом увеличения массива), но я думаю, что я делаю это неправильно. Допустим, у нас есть следующие настройки:

import Data.Vector((++),Vector)
import Prelude hiding ((++))
import Control.Monad.State.Strict

data App = S (Vector Int)

add :: Vector Int -> State App ()
add v1 = modify (\S v2 -> S (v2 ++ v1))

Есть ли add работать в амортизированном O (N) времени в этом случае? Если нет, как я могу сделать add сделать это (мне нужно хранить (forall s. MVector s Int) в государстве?). Есть ли более эффективный способ реализации add?

Answer 1

Я не очень хорошо знаю векторную библиотеку, поэтому я должен придерживаться в основном общих принципов. Оцените его, запустите последовательность добавления, аналогичную ожидаемой в вашем приложении, и посмотрите, какую производительность вы получите. Если это "достаточно хорошо", отлично, придерживайтесь простого кода. Если нет, то перед сохранением (forall s. MVector s Int) в состоянии (которое вы не можете напрямую, кортежи не могут содержать forall-типы, поэтому вам нужно его обернуть), попробуйте улучшить поведение добавления путем преобразования в изменяемые векторы и выполнить конкатенацию перед тем, как заморозить, чтобы получить снова неизменный вектор, примерно

add v1 = do
    S v2 <- get
    let v3 = runST $ do
                m1 <- unsafeThaw v2
                m2 <- unsafeGrow m1 (length v1)
                -- copy contents of v1 behind contents of v2
                unsafeFreeze m2
    put (S v3)

Возможно, вам придется вставить некоторую строгость там. Однако, если unsafeGrow необходимо скопировать, это не гарантирует амортизированное поведение O(n).

Вы можете получить амортизированное поведение O(n)

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