On Mon, Nov 9, 2009 at 8:41 PM, John Harrop <jharrop...@gmail.com> wrote:
> In the meantime, the main thing still missing from Clojure is a convenient
> queue. Lists and vectors both add and remove efficiently only at one end,
> and at the same end for add and remove in both cases. Doubly-linked lists
> can't be made persistent without massive problems, but laziness has its own
> issues:
>
> (defn queue-peek [q] (first q))
> (defn queue-pop [q] (rest q))
> (defn queue-push [q obj] (concat q [obj]))
>
> (let [q (reduce queue-push nil (range 1000000))]
> (reduce (fn [_ q] (queue-pop q)) nil q))
> #<CompilerException java.lang.StackOverflowError (NO_SOURCE_FILE:0)>
>
Solved.
(defn queue-peek [[v i]] (nth v i))
(defn queue-pop [[v i]]
(if (> (* 2 i) (count v))
[(vec (drop (inc i) v)) 0]
[(assoc v i nil) (inc i)]))
(defn queue-push [[v i] obj] [(conj v obj) i])
user=> (reduce queue-push [[] 0] (range 20))
[[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19] 0]
user=> (queue-peek (nth (iterate queue-pop (reduce queue-push [[] 0] (range
20))) 14))
14
user=> (take 20 (iterate queue-pop (reduce queue-push [[] 0] (range 20))))
([[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19] 0]
[[nil 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19] 1]
[[nil nil 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19] 2]
[[nil nil nil 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19] 3]
[[nil nil nil nil 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19] 4]
[[nil nil nil nil nil 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19] 5]
[[nil nil nil nil nil nil 6 7 8 9 10 11 12 13 14 15 16 17 18 19] 6]
[[nil nil nil nil nil nil nil 7 8 9 10 11 12 13 14 15 16 17 18 19] 7]
[[nil nil nil nil nil nil nil nil 8 9 10 11 12 13 14 15 16 17 18 19] 8]
[[nil nil nil nil nil nil nil nil nil 9 10 11 12 13 14 15 16 17 18 19] 9]
[[nil nil nil nil nil nil nil nil nil nil 10 11 12 13 14 15 16 17 18 19]
10]
[[nil nil nil nil nil nil nil nil nil nil nil 11 12 13 14 15 16 17 18 19]
11]
[[12 13 14 15 16 17 18 19] 0]
[[nil 13 14 15 16 17 18 19] 1]
[[nil nil 14 15 16 17 18 19] 2]
[[nil nil nil 15 16 17 18 19] 3]
[[nil nil nil nil 16 17 18 19] 4]
[[nil nil nil nil nil 17 18 19] 5]
[[18 19] 0]
[[nil 19] 1])
As you can see, it uses a vector internally, plus an internal pointer to
where the current "first" element is. Consumed elements are nulled out so if
the queue is used to hold very large objects, stale references to these are
not retained. If more than half the present length of the vector is consumed
entries, the vector is copied to a smaller vector with no consumed entries,
mirroring how things like ArrayList grow by doublings and ensuring the
copying cost is amortized O(1) if there's a long run of queue-consumption.
The queue is persistent and immutable though, much as the underlying vector
is. (Question: can Clojure's vector hold onto stale references in parts that
are unused? Or does it null out array cells that are not part of any
currently existing vector? If the latter, how does it know -- finalizers?
ReferenceQueues?)
As for why I didn't use
(defn queue-peek2 [q] (first q))
(defn queue-pop2 [q] (subvec q 1))
(defn queue-push2 [q obj] (conj q obj))
instead:
user=> (nth (iterate #(subvec (into % [1 2 3]) 3) [0 0 0]) 1000000000)
#<10 minutes of nothing happening>
#<CompilerException java.lang.OutOfMemoryError: Java heap space
(NO_SOURCE_FILE:0)>
Subvec appears to blow up the heap if you keep growing at one end and
chopping at the other for long enough, unlike copying the vector entirely.
Meanwhile:
user=> (nth (iterate #(queue-pop (queue-push % 'foo)) [['foo 'foo] 0])
1000000000)
#<30 minutes of nothing happening>
[[foo foo] 0]
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
