Efficient queue types for Clojure.

[Ken Wesson]

(deftype Queue [chunk1 chunk2 size metadata]
clojure.lang.IObj
(withMeta [this m] (Queue. chunk1 chunk2 size m))
(meta [this] metadata)
clojure.lang.IPersistentStack
(cons [this object] (Queue. chunk1 (conj chunk2 object) (inc size) metadata))
(count [this] size)
(empty [this] (Queue. nil [] 0 metadata))
(equiv [this other] (.equiv (seq this) other))
(seq [this] (seq (lazy-cat chunk1 chunk2)))
(peek [this] (if chunk1 (first chunk1) (first chunk2)))
(pop [this]
(if chunk1
(Queue. (next chunk1) chunk2 (dec size) metadata)
(if-let [nc1 (next chunk2)]
(Queue. nc1 [] (dec size) metadata)
(throw (IllegalStateException.
"Can't pop empty queue")))))
java.lang.Object
(toString [this] (str (seq this))))

(defn queue [& things]
(Queue. (seq things) [] (count things) {}))

The queue stores a seq and a vector; the queue's items are those of
the seq, followed by those of the vector. New items are conjed onto
the vector, which is efficient. Peek looks at the start of the seq,
then if empty the start of the vector, which is efficient. Pop pops
off the seq, if that's not empty. If it is, but the vector isn't, then
it produces a queue whose seq is (next the-old-vector) and whose
vector is empty. This is also O(1).

Essentially, it starts out empty. New items are added to a vector of
newer-stuff. Pop removes from a seq of older-stuff. If the older-stuff
runs out, the current newer-stuff becomes the older-stuff and a new,
empty newer-stuff is started. Items thus move in to the newer-stuff
vector, then into the older-stuff seq, and then get dropped; vectors
get created, populated with new items, and eventually converted into
seqs to be consumed at the other end.

And with that done, a more efficient priority queue, with O(1) pop:

(deftype PriorityQueue [q size]
clojure.lang.IObj
(withMeta [this meta] (PriorityQueue. (with-meta q meta) size))
(meta [this] (meta q))
clojure.lang.IPersistentStack
(cons [this [v pri]]
(PriorityQueue.
(merge-with #(conj %1 (first %2)) q {pri (queue v)})
(inc size)))
(count [this] size)
(empty [this] (PriorityQueue. (sorted-map) 0))
(equiv [this other] (.equiv (seq this) other))
(seq [this] (mapcat val q))
(peek [this] (first (second (first q))))
(pop [this]
(if-let [[pri vq] (first q)]
(let [new-vq (pop vq)]
(if (empty? new-vq)
(PriorityQueue. (dissoc q pri) (dec size))
(PriorityQueue. (assoc q pri new-vq) (dec size))))
(throw (IllegalStateException.
"Can't pop empty priority queue"))))
java.lang.Object
(toString [this] (.toString q)))

(defn priority-queue [& pvs]
(apply conj (PriorityQueue. (sorted-map) 0) (partition 2 pvs)))

For convenience, since priority queue conj expects a vector of [item priority]:

(defn ppush [pri-q item priority & more]
(apply conj pri-q (cons [item priority] (partition 2 more))))

[Mark Engelberg]

Clojure already has a built in queue. The empty queue is:
clojure.lang.PersistentQueue/EMPTY
and then you can use all the usual conj/into/pop/peek functions on it.
For some reason, PersistentQueue is not documented, so new users have
no reason to know about it until they happen to ask about it here.

You might be interested to compare your priority queue implementation
to my "priority map" in 1.3 alpha's contrib, which also supports
updating items' priorities.

As far as I can tell, your priority queue's pop is not O(1), because
the underlying sorted map doesn't support "first" in O(1). It's
actually O(log32#of priorities). My priority map is similar, and I
agree that this behavior is quite fast, but it's worth noting that
it's not truly O(1).

[Ken Wesson]

On Sat, Jan 22, 2011 at 2:14 PM, Mark Engelberg
<mark.en...@gmail.com> wrote:
> Clojure already has a built in queue.  The empty queue is:
> clojure.lang.PersistentQueue/EMPTY
> and then you can use all the usual conj/into/pop/peek functions on it.
> For some reason, PersistentQueue is not documented, so new users have
> no reason to know about it until they happen to ask about it here.
>
> You might be interested to compare your priority queue implementation
> to my "priority map" in 1.3 alpha's contrib, which also supports
> updating items' priorities.
>
> As far as I can tell, your priority queue's pop is not O(1), because
> the underlying sorted map doesn't support "first" in O(1).  It's
> actually O(log32#of priorities).

log32 of max 2147483648 map entries is max 6.2. It's O(1) for all
intents and purposes.

[Chouser]

On Sat, Jan 22, 2011 at 2:14 PM, Mark Engelberg
<mark.en...@gmail.com> wrote:

Clojure's sorted collections are binary trees thus log2, not log32
like the hashed collections.

--Chouser
http://joyofclojure.com/

[Mark Engelberg]

On Sat, Jan 22, 2011 at 2:29 PM, Chouser <cho...@gmail.com> wrote:
> Clojure's sorted collections are binary trees thus log2, not log32
> like the hashed collections.

Good point. My mistake.

[Ken Wesson]

That makes it up to a constant factor of 32 slower if there's a REAL
huge amount of stuff at the (currently) most urgent priority. Still
damned good compared to the version I posted this morning.

[e]

interesting.  maybe I can change my interface in this thing I abandoned a while back: http://code.google.com/p/jc-pheap/

to match that of the contrib, "priority map".  I had gotten stuck figuring out the right interface/usage/idioms for clojure and kinda messed the whole thing up in later checkins.  Then clojure went to GIT and I pretty much lost the remaining interesting having started in svn.

but now I have a reason again... if I can ever get a comfortable programming environment in clojure (never was able to before).  I can see how it works compared to work others are doing.

thanks.

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en