Как я могу обеспечить амортизацию 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 раза, что гарантирует, что каждый элемент копируется в среднем не более двух раз