Эффективная очередь в Haskell
Если это находится на единственной машине, Именованные каналы дает Вам лучшую производительность и может быть реализован с инфраструктура дистанционной работы , а также WCF. Или можно просто непосредственно использовать Система. IO.Pipes.
3 ответа
Вы всегда можете просто использовать Data.Sequence .
В качестве альтернативы хорошо известная реализация чисто функциональной очереди состоит в использовании двух списков. Один для постановки в очередь, а другой - для удаления. Enqueue просто минус список enqueue. Dequeue занимает начало списка удаления из очереди. Если список вывода из очереди короче, чем список постановки в очередь, пополните его, перевернув список постановки в очередь. См. Чисто функциональные структуры данных Криса Окасаки.
Несмотря на то, что эта реализация использует обратное , амортизированные временные затраты на это асимптотически несущественны. Это работает так, что для каждой постановки в очередь у вас возникает временная задолженность в размере Θ (1) для пополнения списка удаления из очереди. Таким образом, ожидаемое время постановки в очередь не более чем в два раза больше, чем время постановки в очередь. Это постоянный фактор,
Является ли Data.Dequeue тем, что вы ищете?
(В нем нет reverse , но вы можете легко добавить его и отправьте патч автору.)
На самом деле я не являюсь пользователем Haskell, но я нашел сообщение в блоге , в котором утверждается, что описывается очередь Haskell, с которой можно работать за амортизированное постоянное время. Он основан на дизайне превосходных чисто функциональных структур данных Криса Окасаки.