Cola inmutable en Clojure

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

Solo necesita dos operaciones, en cola y dequeue con la semántica habitual.

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 en cola y dequeue.

Fuente

2010-06-28 mikera

Para evitar que alguien escriba sobre cómo se pueden usar las listas de contras para implementar las pilas push/pop (como casi lo hice), no olvides que la pregunta se refiere a * colas *. :-) –

Acabo de notar que hay una clase llamada PersistentQueue en la última versión 1.2 de la fuente Clojure Java .... puede ser la respuesta a mi propia pregunta – mikera

Ha estado allí desde siempre (solo comprobado con 1.1, pero creo que es más antiguo) que eso). Tenga en cuenta que no hay una función de fábrica ni una sintaxis del lector proporcionadas por defecto; use 'clojure.lang.PersistentQueue/EMPTY' para obtener una instancia vacía. Luego 'conj',' pop' y 'peek' funcionan como deberían con una cola. Ver p. mi respuesta a esta pregunta: http://stackoverflow.com/questions/2760017 para algún código escrito tanto con 'c.l.PQ' como con' LinkedBlockingQueue' de Java. –

Problema solucionado: solución para otras personas que lo pueden encontrar útil.

He encontrado 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 yo puedo ver, que actualmente es necesario utilizar el Java interoperabilidad para crear la instancia sino como Michal amablemente señaló que puede utilizar vistazo, pop y conj posteriormente.

Fuente

2010-06-28 22:46:23 mikera

PersistentQueue es de hecho su mejor opción. Para referencia futura, aquí hay una tabla que resume las características/garantías de rendimiento de las estructuras de datos de clojure: http://www.innoq.com/blog/st/2010/04/clojure_performance_guarantees.html – dvogel

¿Por qué usar 'atom'? –

@ raxod502 ¿Hay algún problema con el uso de un átomo en esta situación? – dgellow

Utilizo la siguiente función queue 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.

peek - conseguir la cabeza
pop - devuelve un nuevo PersistentQueue sin la cabeza
conj - añadir el artículo a la cola
vacío? - cierto si vacías
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])))))

Fuente

2015-01-28 19:39:35 miner49r

Clojure realmente podrían beneficiarse de una cola literal. 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 del encabezado de la cola y la otra la cola. enqueue se agrega a la primera lista, dequeue emerge de este último. La mayoría de las funciones ISeq se implementan de manera trivial.

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

Feliz queue ing!

Fuente

2016-10-08 00:28:11 CurtainDog

Respuesta

Cuestiones relacionadas