Неизменяемая очередь в Clojure

Каков наилучший способ получить простой, эффективный неизменный тип данных очереди в Clojure?

Требуется только две операции: enqueue и dequeue с обычной семантикой.

Я, конечно, рассматривал списки и векторы, но я понимаю, что они имеют сравнительно низкую производительность (т.е. O (n) или хуже) для модификаций в конце и начале соответственно - поэтому не идеальны для очередей!

В идеале мне нужна правильная постоянная структура данных с O (log n) для операций в очереди и деактивации.

Ответ 1

Проблема решена - решение для других, которые могут оказаться полезными.

Я обнаружил, что Clojure имеет класс clojure.lang.PersistentQueue, который делает то, что необходимо.

Вы можете создать такой экземпляр:

(def x (atom clojure.lang.PersistentQueue/EMPTY))

Насколько я могу судить, в настоящее время вам нужно использовать Java-взаимодействие для создания экземпляра, но поскольку Michal с умыслом указал, вы можете использовать peek, pop и conj впоследствии.

Ответ 2

Я использую следующую функцию queue для создания PersistentQueue. При желании вы можете захотеть иметь метод печати и считыватель данных, если вы собираетесь печатать и читать очереди.

Обычные функции Clojure уже реализованы для PersistentQueue.

peek - получить головку
pop - возвращает новый PersistentQueue без головы
conj - добавить элемент в хвост
пустой? - true, если пустой
seq - содержимое в виде последовательности (списка)


    (defn queue
      ([] clojure.lang.PersistentQueue/EMPTY)
      ([coll] (reduce conj clojure.lang.PersistentQueue/EMPTY coll)))

    (defmethod print-method clojure.lang.PersistentQueue
      [q ^java.io.Writer w]
      (.write w "#queue ")
      (print-method (sequence q) w))

    (comment
       (let [*data-readers* {'queue #'queue}]
         (read-string (pr-str (queue [1 2 3])))))

Ответ 3

Clojure может действительно выиграть от литерала очереди. Это было бы более чистым (и более портативным), чем полагаться на Java interop.

Однако, это не так сложно свернуть вашу собственную переносимую постоянную очередь, просто используя обычные предметы домашнего обихода, такие как списки.

Рассмотрим очередь как два списка, одна из которых содержит головную часть очереди, а другая - хвост. enqueue добавляет в первый список, dequeue выскакивает из последнего. Большинство функций ISeq реализованы тривиально.

Вероятно, единственная сложная часть - это то, что происходит, когда хвост пуст, и вы хотите dequeue. В этом случае список заголовков reverse d и становится новым хвостом, а пустой список становится новым списком голов. Я полагаю, что даже с накладными расходами reverse, что enqueue и dequeue остаются O(1), хотя k будет, конечно, выше, чем вектор ванили.

Счастливый queue ing!