File d'attente immuable en Clojure

Question

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

Il ne nécessite que deux opérations, enqueue et dequeue, avec la sémantique habituelle.

J'ai envisagé les listes et les vecteurs, bien sûr, mais je crois savoir 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 - ce n'est donc pas l'idéal pour les files d'attente !

Idéalement, j'aimerais avoir une structure de données persistante avec O(log n) pour les opérations d'enqueue et de dequeue.

Answer 1

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

J'ai découvert que Clojure dispose de la classe clojure.lang.PersistentQueue qui fait ce dont on a besoin.

Vous pouvez créer une instance comme ceci :

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

D'après ce que je vois, vous devez actuellement utiliser l'interop Java pour créer l'instance, mais comme Michal l'a fait remarquer, vous pouvez utiliser peek, pop et conj par la suite.

Answer 2

J'utilise la fonction suivante queue pour créer une PersistentQueue. En option, vous pouvez avoir une méthode d'impression et un lecteur de données si vous avez l'intention d'imprimer et de lire les files d'attente.

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

• coup d'oeil -- obtenir la tête
• pop -- renvoie une nouvelle PersistentQueue sans la tête
• conj -- ajoute un élément à la queue
• vide ? -- vrai 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 pourrait vraiment bénéficier d'une queue littérale. Cela serait plus propre (et plus portable) que de dépendre de l'interopérabilité avec Java.

Cependant, il n'est pas si difficile de créer sa propre file d'attente persistante portable, en utilisant simplement des éléments domestiques ordinaires comme les listes.

Considérez la file d'attente comme deux listes, l'une fournissant la partie tête de la file, et l'autre la partie queue. enqueue s'ajoute à la première liste, dequeue les pops de ces derniers. La plupart ISeq sont implémentées de manière triviale.

La seule partie délicate est probablement ce qui se passe lorsque la queue est vide et que l'on veut dequeue . Dans ce cas, la liste de tête est reverse d et devient la nouvelle queue, et la liste vide devient la nouvelle tête de liste. Je pense que, même avec la surcharge de l'option reverse que enqueue y dequeue rester O(1) bien que le k va être plus élevé qu'un vecteur vanille bien sûr.

Joyeux queue de l'homme !