algorithm - Cola inmutable en Clojure

data-structures queue

Question

¿Cuál es la mejor manera de obtener un tipo de datos de cola inmutable simple y eficiente en Clojure?

Solo necesita dos operaciones, enqueue y dequeue con la semántica usual.

Consideré listas y vectores por supuesto, pero entiendo que tienen un rendimiento comparativamente pobre (es decir, O (n) o peor) para modificaciones al final y al principio respectivamente, ¡así que no es ideal para colas!

Idealmente, me gustaría tener una estructura de datos persistente adecuada con O (log n) para las operaciones tanto en cola como dequeue.

Answer 1

Clojure realmente podría beneficiarse de un literal de cola. Esto sería más limpio (y más portátil) que depender de la interoperabilidad de Java.

Sin embargo, no es tan difícil rodar su propia cola persistente portátil, simplemente utilizando elementos comunes del hogar como listas.

Considere la cola como dos listas, una que proporciona la parte principal de la cola y la otra la cola. enqueue agrega a la primera lista, dequeue pops de este último. La mayoría de ISeq funciones de ISeq se implementan de manera trivial.

Probablemente, la única parte difícil es lo que sucede cuando la cola está vacía y quieres dequeue . En ese caso, la lista principal es d reverse y se convierte en la nueva cola, y la lista vacía se convierte en la nueva lista principal. Creo, incluso con la sobrecarga del reverse , que dequeue y dequeue siguen siendo O(1) , aunque la k va a ser más alta que un vector vainilla, por supuesto.

Feliz queue ing!

Answer 2

Problema resuelto - solución para otros que pueden encontrarlo útil.

Descubrí que Clojure tiene la clase clojure.lang.PersistentQueue que hace lo que se necesita.

Puede crear una instancia como esta:

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

Por lo que puedo ver, actualmente necesita usar la interoperabilidad de Java para crear la instancia, pero como Michal le señaló amablemente, puede usar peek, pop y conj posteriormente.

Answer 3

Uso la siguiente queue funciones para crear una PersistentQueue. Opcionalmente, es posible que desee tener un método de impresión y un lector de datos si va a imprimir y leer las colas.

Las funciones habituales de Clojure ya están implementadas para PersistentQueue.

• vistazo - obtener la cabeza
• pop - devuelve un nuevo PersistentQueue sin la cabeza
• conj - agregar elemento a la cola
• ¿vacío? - verdadero si está vacío
• seq - contenido como una secuencia (lista)

(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])))))