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 -~----------~----~----~----~------~----~------~--~---