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

Reply via email to