O (1) кольцевой буфер в haskell?
Я работаю над маленьким проектом понятия в Haskell, который требует кольцевого буфера. Мне удалось создать буферное использование массивы, который имеет O (1) вращение, но конечно требует O (N) для вставки/удаления. Я нашел реализацию с помощью списков, который, кажется, берет O (1) для вставки и удаления, но так как это ведет левый и правый список, пересекая определенную границу, когда вращение возьмет O (N) время. На императивном языке я мог реализовать вдвойне связанный кольцевой буфер с O (1) вставка, удаление и вращение. Я думаю, что это не возможно на чисто функциональном языке как Haskell, но я хотел бы знать, неправ ли я.
3 ответа
Мы используем инструмент с открытым исходным кодом Hudson . Это действительно хороший инструмент для автоматического построения. Но это не только для строительства. Вы можете использовать его для выполнения тестов, предоставления отчетов о покрытии кода, отправки уведомлений по электронной почте и т.д.
(Наша платформа разработки в основном linux + java)
-121--3320611-Пока вы не назовете изображение чем-то очевидным, например, emailadress.png, вы должны быть в полной безопасности - я думаю.
-121--3594941- Монада ST позволяет описывать и выполнять императивные алгоритмы в Haskell. Можно использовать STRef s для изменяемых указателей списка двойных связей.
Автономные алгоритмы, описанные с помощью ST , выполняются с помощью runST . Различные выполнения runST не могут совместно использовать структуры данных ST ( STRef , STAray ,..).
Если алгоритм не является «автономным» и структура данных должна поддерживаться с операциями ввода-вывода, выполняемыми в промежутках между его использованием, можно использовать stToIO для доступа к нему в IO monad.
Что касается того, является ли это чисто функциональным или нет - полагаю, это не так?
Похоже, вам может понадобиться что-то посложнее (поскольку вы упомянули двусвязные списки), но, возможно, это поможет. Эта функция действует как map над изменяемым циклическим списком:
mapOnCycling f = concat . tail . iterate (map f)
Используйте как:
*Main> (+1) `mapOnCycling` [3,2,1]
[4,3,2,5,4,3,6,5,4,7,6,5,8,7,6,9,8,7,10,9...]
А вот тот, который действует как mapAccumL:
mapAccumLOnCycling f acc xs =
let (acc', xs') = mapAccumL f acc xs
in xs' ++ mapAccumLOnCycling f acc' xs'
В любом случае, если вы хотите уточнить, что именно ваш структура данных должна уметь «делать». Мне было бы действительно интересно услышать об этом.
РЕДАКТИРОВАТЬ : как упоминал camccann, для этого можно использовать Data.Sequence , что, согласно документации, должно дать вам временную сложность O1 (существует ли такая вещь, как амортизированное время O1?) для просмотра или добавления элементов как к левой, так и к правой сторонам последовательности, а также для изменения концов по ходу. Я не уверен, будет ли это иметь нужную вам производительность.
Вы можете рассматривать «текущее местоположение» как левый конец последовательности. Здесь мы перемещаемся вперед и назад по последовательности, создавая бесконечный список значений. Извините, если он не компилируется, у меня сейчас нет GHC:
shuttle (viewl-> a <: as) = a : shuttle $ rotate (a+1 <| as)
where rotate | even a = rotateForward
| otherwise = rotateBack
rotateBack (viewr-> as' :> a') = a' <| as'
rotateForward (viewl-> a' <: as') = as' |> a'
Если вы можете иметь дело с амортизированными O (1) операциями, вы, вероятно, могли бы использовать либо Data.Sequence из пакета контейнеров, либо Data.Dequeue из пакета dequeue. В первом случае используются деревья пальцев , а во втором - «Banker's Dequeue» из чисто функциональных структур данных Okasaki (предыдущая онлайн-версия здесь ).