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

Question

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

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

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

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

Answer 1

Проблема решена - решение для тех, кто может найти ее полезной.

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

Вы можете создатьПример, подобный следующему:

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

Насколько я понимаю, в настоящее время вам нужно использовать взаимодействие Java для создания экземпляра, но, как подсказал Михал, вы можете использовать peek, pop и coni впоследствии.

Answer 2

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

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

• заглянуть - получить голову
• pop - возвращает новый PersistentQueue без заголовка
• кон - добавить предмет в хвост
• пусто? - 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])))))

Answer 3

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

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

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

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

Happyqueue ING!