File d'attente immuable dans Clojure

Question

Quelle est la meilleure façon d'obtenir un type de données de file d'attente immuable simple et efficace dans Clojure?

Il suffit de deux opérations, enqueue et dequeue avec la sémantique habituelle. Je considérais les listes et les vecteurs bien sûr, mais je comprends qu'ils ont des performances relativement médiocres (c'est-à-dire O (n) ou pire) pour les modifications à la fin et au début respectivement - donc pas idéal pour les files d'attente!

Idéalement, je voudrais une structure de données persistante appropriée avec O (log n) pour les enqueue et les opérations dequeue.

Answer 1

Problème résolu - solution pour d'autres personnes qui pourraient trouver cela utile.

J'ai trouvé que Clojure a la classe clojure.lang.PersistentQueue qui fait ce qui est nécessaire.

Vous pouvez créer une instance comme ceci:

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

Pour autant que je peux voir, vous avez besoin actuellement d'utiliser Interop Java pour créer l'instance mais comme Michal obligeamment a souligné que vous pouvez utiliser PEEK, pop et conj par la suite.

Answer 2

J'utilise la fonction suivante queue pour créer un PersistentQueue. Vous pouvez éventuellement avoir une méthode d'impression et un lecteur de données si vous imprimez et lisez les files d'attente.

Les fonctions Clojure habituelles sont déjà implémentées pour PersistentQueue.

• coup d'oeil - obtenir la tête
• pop - retourne une nouvelle PersistentQueue sans la tête
• conj - ajouter l'article à la queue
• vide? - true si vide
• seq - contenu comme une séquence (liste)

    (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 pourraient vraiment bénéficier d'une file d'attente littérale. Ce serait plus propre (et plus portable) que de se fier à Java interop.

Cependant, ce n'est pas difficile de rouler votre propre file d'attente permanente portable, tout en utilisant des articles ménagers ordinaires comme des listes.

Considérons la file d'attente comme deux listes, l'une fournissant la partie tête de la file d'attente, et l'autre la queue. enqueue ajoute à la première liste, dequeue apparaît de ce dernier. La plupart des fonctions ISeq sont implémentées de manière triviale.

Probablement la seule partie délicate est ce qui se passe lorsque la queue est vide et que vous voulez dequeue. Dans ce cas, la liste de tête est reverse d et devient la nouvelle queue, et la liste vide devient la nouvelle liste de tête. Je crois, même avec les frais généraux du reverse, que enqueue et dequeue restent O(1), bien que le k va être supérieure à un vecteur de vanille bien sûr.

Heureux queue ing!