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

У меня есть приложение, в котором эффективно использовать векторы для одной части кода. Однако во время вычислений мне нужно отслеживать некоторые элементы. Я слышал, что вы можете получить амортизированную конкатенацию 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?


vector haskell amortized-analysis
person HaskellElephant    schedule 27.10.2011    source источник
comment
@hvr: Нет, это не то, чего я хочу. Я почти уверен, что делаю это неправильно в своем вопросе. Однако я не очень хорошо знаком с библиотекой Data.Vector, и хотя в документации (++) указано только, что это O(m+n) в худшем случае, она все же может иметь O(n ) амортизированное время выполнения.   -  person HaskellElephant    schedule 27.10.2011
comment
Поэтому я ненавижу, когда люди в StackOverflow отвечают на вопросы вопросами, но я собираюсь это сделать :P - Почему вы думаете, что делаете это неправильно? Я предполагаю, что вы используете State по какой-то причине, не связанной с этим вопросом, поэтому, если вы удалите вещи, связанные с State, станет ясно, что вы не делаете ничего сумасшедшего: ‹!-- language: lang-hs --› add :: Vector Int -> Vector Int -> Vector Int add v1 v2 = v1 ++ v2. Вы заметили, что в документации говорится, что это выполняется за время O(n + m); что заставило вас поверить, что он должен работать быстрее?   -  person mergeconflict    schedule 27.10.2011
comment
Неправильно может быть слишком сильным, я просто хотел сказать, что я понимаю, что добавление может закончиться тем, что в худшем случае O (n ^ 2) *. Также обратите внимание, что хотя что-то может работать в худшем случае O(n+m), оно может работать в амортизированном O(n), причина, по которой я думал, что это может быть достигнуто. заключается в том, что MVector может расти (hackage.haskell.org/packages/archive/vector/0.9/doc/html/), и я думаю, что где-то это слышал. Причина, по которой я включил состояние, и я знаю, что это неясно, заключается в том, что это то, что я делаю в своем приложении, и это не совсем не связано, поскольку я могу хранить какой-то другой тип.   -  person HaskellElephant    schedule 27.10.2011
comment
Связанный дополнительный вопрос: stackoverflow.com/q/7978130/283240   -  person HaskellElephant    schedule 04.11.2011

Ответы (1)


arrow_upward
2
arrow_downward

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

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 раза, что гарантирует, что каждый элемент копируется в среднем не более двух раз
person Daniel Fischer    schedule 27.10.2011
comment
Порядок добавления был неправильным в вопросе, поэтому я изменил его. Первый случай В вашем вопросе то, что мне нужно... - person HaskellElephant; 27.10.2011
comment
Обновлено, чтобы соответствовать исправленному вопросу. - person Daniel Fischer; 27.10.2011
comment
Я могу ошибаться, но я думаю, чтобы получить амортизированный O (n), вам не нужен коэффициент роста, равный 2. Я думаю, что он просто должен быть больше 1 (но вам нужно проверить, что вы растете по крайней мере на 1 элемент с небольшими списками). - person Thomas Eding; 29.10.2011
comment
Конечно, вы правы, подойдет любой множитель q > 1 с ограничением числа копий q/(q-1). Если вас беспокоит память, предпочтительнее могут быть меньшие коэффициенты, я выбрал 2, потому что это просто и количество копий невелико. - person Daniel Fischer; 29.10.2011