On Wed, Jul 15, 2009 at 12:58 PM, Mark Engelberg <mark.engelb...@gmail.com>wrote: > > It looks like stack-rot is going to be the bottleneck in your app > since it requires traversing the whole vector to build the new one, > but I think the list-based implementation would be a bit worse, so I > think your choice to use vectors here is sound. > > For stack-dropn and stack-rot to both be fast, I think that you really > want to use a deque. Unfortunately, Clojure doesn't have a built-in > deque, and I don't see one in contrib, but you could look at > clojure.lang.PersistentQueue and read Okasaki's Functional Data > Structures to draw some inspiration.
What's needed here is a ring buffer. It shouldn't be hard to implement one atop a pair of a clojure vec, a true-count, and a start-offset. Rotation is then very cheap: replace v with (assoc v (- (+ start-offset true-count) (count v)) (get v start-offset)) and start-offset with (let [s-o (inc start-offset)] (if (= (count v) s-o) 0 s-o)). Dropn is similarly: true-count becomes (- n true-count) and start-offset (mod (+ start-offset n) (count v)). Indexing is cheap: (get v (mod (+ start-offset (mod index true-count)) (count v))) and peek is even cheaper: (get v start-offset). (Maybe add code to handle empty, that is, (= 0 true-count)). The tricky thing is push. If (= true-count (count v)) the vector needs to be copied to a larger vector. You might want to double the size, leaving the unused elements nil: v becomes (vec (concat (drop start-offset v) (take start-offset v) [new-element] (repeat true-count nil))), true-count is inc'd as normal for a push, and start-offset reset to zero. Doubling the size whenever the vector must grow causes the cost of copying the vector to be asymptotically constant per push, instead of linear in the average size of the vector at the time of a push. (Ironically, the vector probably has this behavior under the hood, like java.util.ArrayList, but we need it again because (vec (concat (drop start-offset v) (take start-offset v) [new-element] (repeat true-count nil))) has linear time-complexity in vector length.) You'd actually want to use a structmap for the above if you want to have multiple ring buffers, with struct keys :count, :offset, and :vector or similarly. Depending on the application, you might want to make the values for these keys be refs and have the ring buffer operations use dosync, though you could instead use a single ref per instance of the structmap. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
