On Thu, Jul 16, 2009 at 1:52 AM, John Harrop<jharrop...@gmail.com> wrote:
> 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.
>
FWIW since Java 1.6 there's a java.util.Deque (implemented as
RingBuffer) interface with java.util.ArrayDeque implementation, and a
java.util.concurrent.BlockingDeque interface with
java.util.concurrent.LinkedBlockingDeque implementation.
With the Deque interface, you can rotate both directions pretty easily
and the rest of the stack like methods are pretty straightforward:
(import '(java.util ArrayDeque))
(let [deque (ArrayDeque. '(1 2 3 4))]
(println deque)
; rot forward
(.addLast deque (.removeFirst deque))
(println deque)
; rot backward
(.addFirst deque (.removeLast deque))
(println deque))
But then again, it's a Java collection and not a Clojure one.
Cheers,
Daniel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
