Gaving slept on it I realize that by adding before popping I allowed the
buffer to grow to n+1 thus causing a realloc.
(defn drop-last [n coll]
(reducer coll
(fn [f1]
(let [buffer (java.util.ArrayDeque. (int n))]
(fn self
([] (f1))
([ret x]
(let [ret (if (= (count buffer) n)
(f1 ret (.pop buffer))
ret)]
(.add buffer x)
ret)))))))
(defn take-last [n coll]
(reify clojure.core.protocols.CollReduce
(coll-reduce [this f1]
(clojure.core.protocols/coll-reduce this f1 (f1)))
(coll-reduce [_ f1 init]
(clojure.core.protocols/coll-reduce
(clojure.core.protocols/coll-reduce
coll
(fn [^java.util.Deque q x]
(when (= (count q) n)
(.pop q))
(.add q x)
q) (java.util.ArrayDeque. (int n)))
f1 init))))
On Thu, Aug 8, 2013 at 3:34 PM, Christophe Grand <[email protected]>wrote:
> ArrayDeque based versions:
>
>
> (defn drop-last [n coll]
> (reducer coll
> (fn [f1]
> (let [buffer (java.util.ArrayDeque. (int n))]
>
> (fn self
> ([] (f1))
> ([ret x]
> (.add buffer x)
> (if (<= (count buffer) n)
> ret
> (f1 ret (.pop buffer)))))))))
>
>
> (defn take-last [n coll]
> (reify clojure.core.protocols.CollReduce
> (coll-reduce [this f1]
> (clojure.core.protocols/coll-reduce this f1 (f1)))
> (coll-reduce [_ f1 init]
> (clojure.core.protocols/coll-reduce
> (doto (clojure.core.protocols/coll-reduce
> coll
> (fn [^java.util.Deque q x]
> (.add q x)
> (when (> (count q) n)
> (.pop q))
> q) (java.util.ArrayDeque. (int n))) prn)
> f1 init))))
>
>
>
> On Thu, Aug 8, 2013 at 3:16 PM, Christophe Grand <[email protected]>wrote:
>
>> You need to use a buffer to defer calls to the reduced function
>>
>> (defn drop-last [n coll]
>> (reducer coll
>> (fn [f1]
>> (let [buffer
>> (atom clojure.lang.PersistentQueue/EMPTY)]
>> (fn self
>> ([] (f1))
>> ([ret x]
>> (let [b (swap! buffer conj x)]
>> (if (<= (count @buffer) n)
>> ret
>> (do
>> (swap! buffer pop)
>> (f1 ret (peek b)))))))))))
>>
>> An array or a ring buffer should be used instead of the atom and
>> persistent queue combo to reduce allocation.
>>
>> take-last is harder because you can't know when the reduction is over
>> when using #'reducer, so you have to implement CollReduce yourself:
>>
>> (defn take-last [n coll]
>> (reify clojure.core.protocols.CollReduce
>> (coll-reduce [this f1]
>> (clojure.core.protocols/coll-reduce this f1 (f1)))
>> (coll-reduce [_ f1 init]
>> (clojure.core.protocols/coll-reduce
>> (clojure.core.protocols/coll-reduce
>> coll
>> (fn [q x]
>> (let [q (conj q x)]
>> (if (<= (count q) n)
>> q
>> (pop q)))) clojure.lang.PersistentQueue/EMPTY)
>> f1 init))))
>>
>> again, use of a mutable array/buffer would be preferable.
>>
>> hth,
>>
>> Christophe
>>
>> On Thu, Aug 8, 2013 at 1:00 PM, Jozef Wagner <[email protected]>wrote:
>>
>>> Is it possible to implement efficient butlast (and drop-last, take-last)
>>> with reducers? The only solution I can think of needs additional reduce to
>>> compute count, which may often be undesirable.
>>>
>>> Or is it OK to say that reducers are not designed for such cases?
>>>
>>> JW
>>>
>>> --
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Clojure" group.
>>> To post to this group, send email to [email protected]
>>> Note that posts from new members are moderated - please be patient with
>>> your first post.
>>> To unsubscribe from this group, send email to
>>> [email protected]
>>> For more options, visit this group at
>>> http://groups.google.com/group/clojure?hl=en
>>> ---
>>> You received this message because you are subscribed to the Google
>>> Groups "Clojure" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to [email protected].
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>>
>>
>>
>>
>> --
>> On Clojure http://clj-me.cgrand.net/
>> Clojure Programming http://clojurebook.com
>> Training, Consulting & Contracting http://lambdanext.eu/
>>
>
>
>
> --
> On Clojure http://clj-me.cgrand.net/
> Clojure Programming http://clojurebook.com
> Training, Consulting & Contracting http://lambdanext.eu/
>
--
On Clojure http://clj-me.cgrand.net/
Clojure Programming http://clojurebook.com
Training, Consulting & Contracting http://lambdanext.eu/
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
