2012/7/24 Laurent PETIT <[email protected]>
> And I guess it is so because into, being called numerous times, keeps
> transforming bigger and bigger vectors into transient vectors, and back to
> persistent vectors, etc.
Answering to self: I was wrong, problem does not seem to be with internal
use of transients inside into, since removing them makes things worse:
=> (defn my-into
"Returns a new coll consisting of to-coll with all of the items of
from-coll conjoined."
{:added "1.0"
:static true}
[to from]
(reduce conj to from))
(defrecord Tree [h l r])
(defn generate-tree [c]
(when-let [s (seq c)]
(let [lr (generate-tree (rest s))]
(Tree. (first s) lr lr))))
(defn to-list
([t] (to-list t []))
([t b]
(if t
(my-into (conj (to-list (:l t) b) (:h t)) (to-list (:r t) b))
b)))
(defn tree [n]
(generate-tree (range 1 n)))
(let [t (tree 21)]
(dotimes [_ 10]
(time
(dotimes [_ 1]
(println (count (to-list t)))))))
#'user/my-into
user.Tree
#'user/generate-tree
#'user/to-list
#'user/tree
1048575
"Elapsed time: 1121.971 msecs"
1048575
"Elapsed time: 969.479 msecs"
1048575
"Elapsed time: 991.333 msecs"
1048575
"Elapsed time: 940.975 msecs"
1048575
"Elapsed time: 956.785 msecs"
1048575
"Elapsed time: 1007.633 msecs"
1048575
"Elapsed time: 984.384 msecs"
1048575
"Elapsed time: 965.166 msecs"
1048575
"Elapsed time: 955.469 msecs"
1048575
"Elapsed time: 963.43 msecs"
nil
>
>
> 2012/7/24 Laurent PETIT <[email protected]>
>
>> Oh, and finally, note that even without transients, you get 6x better
>> perf by not calling into directly:
>>
>> => (defrecord Tree [h l r])
>>
>>
>> (defn generate-tree [c]
>> (when-let [s (seq c)]
>> (let [lr (generate-tree (rest s))]
>> (Tree. (first s) lr lr))))
>>
>> (defn to-list
>> ([t] (to-list t []))
>>
>> ([t b]
>> (if t
>> (let [b (to-list (:l t) b),
>> b (conj b (:h t)),
>>
>> b (to-list (:r t) b)]
>> b)
>> b)))
>> (defn tree [n]
>> (generate-tree (range 1 n)))
>>
>> (let [t (tree 21)]
>> (dotimes [_ 10]
>> (time
>> (dotimes [_ 1]
>> (println (count (to-list t)))))))
>> user.Tree
>> #'user/generate-tree
>> #'user/to-list
>> #'user/tree
>> 1048575
>> "Elapsed time: 174.14 msecs"
>> 1048575
>> "Elapsed time: 124.218 msecs"
>> 1048575
>> "Elapsed time: 130.186 msecs"
>> 1048575
>> "Elapsed time: 109.883 msecs"
>> 1048575
>> "Elapsed time: 104.221 msecs"
>> 1048575
>> "Elapsed time: 98.387 msecs"
>> 1048575
>> "Elapsed time: 98.21 msecs"
>> 1048575
>> "Elapsed time: 103.543 msecs"
>> 1048575
>> "Elapsed time: 98.663 msecs"
>> 1048575
>> "Elapsed time: 101.913 msecs"
>> nil
>> => (defrecord Tree [h l r])
>>
>>
>> (defn generate-tree [c]
>> (when-let [s (seq c)]
>> (let [lr (generate-tree (rest s))]
>> (Tree. (first s) lr lr))))
>>
>> (defn to-list
>> ([t] (to-list t []))
>>
>> ([t b]
>> (if t
>> (into (conj (to-list (:l t) b) (:h t)) (to-list (:r t) b))
>>
>> b)))
>> (defn tree [n]
>> (generate-tree (range 1 n)))
>>
>> (let [t (tree 21)]
>> (dotimes [_ 10]
>> (time
>> (dotimes [_ 1]
>> (println (count (to-list t)))))))
>> user.Tree
>> #'user/generate-tree
>> #'user/to-list
>> #'user/tree
>> 1048575
>> "Elapsed time: 1149.562 msecs"
>> 1048575
>> "Elapsed time: 846.225 msecs"
>> 1048575
>> "Elapsed time: 605.007 msecs"
>> 1048575
>> "Elapsed time: 604.409 msecs"
>> 1048575
>> "Elapsed time: 625.605 msecs"
>> 1048575
>> "Elapsed time: 626.066 msecs"
>> 1048575
>> "Elapsed time: 605.502 msecs"
>> 1048575
>> "Elapsed time: 621.007 msecs"
>> 1048575
>> "Elapsed time: 606.064 msecs"
>> 1048575
>> "Elapsed time: 642.739 msecs"
>> nil
>>
>>
>> 2012/7/23 Laurent PETIT <[email protected]>
>>
>>> 2012/7/23 Mark Engelberg <[email protected]>
>>>
>>>> As David was posting his code, I was wrapping up my own experimentation
>>>> with how transients apply here. Mine is similar, but doesn't use pattern
>>>> matching -- seems a bit faster:
>>>>
>>>>
>>>> (defrecord Tree [h l r])
>>>>
>>>> (defn generate-tree [c]
>>>> (when-let [s (seq c)]
>>>> (let [lr (generate-tree (rest s))]
>>>> (Tree. (first s) lr lr))))
>>>>
>>>> (defn to-list
>>>> ([t] (persistent! (to-list t (transient []))))
>>>> ([t b]
>>>> (if t
>>>> (let [b (to-list (:l t) b),
>>>> b (conj! b (:h t)),
>>>> b (to-list (:r t) b)]
>>>> b)
>>>> b)))
>>>>
>>>>
>>> True,
>>>
>>> and notice you can also drop records altogether:
>>>
>>>
>>> (defn generate-tree [c]
>>> (when-let [s (seq c)]
>>> (let [lr (generate-tree (rest s))]
>>> [(first s) lr lr])))
>>>
>>>
>>> (defn to-list
>>> ([t] (persistent! (to-list t (transient []))))
>>> ([t b]
>>> (if t
>>> (let [b (to-list (t 1) b),
>>> b (conj! b (t 0)),
>>> b (to-list (t 2) b)]
>>> b)
>>> b)))
>>>
>>> (defn tree [n]
>>> (generate-tree (range 1 n)))
>>>
>>> (let [t (tree 21)]
>>> (dotimes [_ 10]
>>> (time
>>> (dotimes [_ 1]
>>> (println (count (to-list t)))))))
>>>
>>> 1048575
>>> "Elapsed time: 346.446 msecs"
>>> 1048575
>>> "Elapsed time: 37.2 msecs"
>>> 1048575
>>> "Elapsed time: 32.795 msecs"
>>> 1048575
>>> "Elapsed time: 31.655 msecs"
>>> 1048575
>>> "Elapsed time: 45.388 msecs"
>>> 1048575
>>> "Elapsed time: 30.612 msecs"
>>> 1048575
>>> "Elapsed time: 27.141 msecs"
>>> 1048575
>>> "Elapsed time: 40.887 msecs"
>>> 1048575
>>> "Elapsed time: 27.526 msecs"
>>> 1048575
>>> "Elapsed time: 26.747 msecs"
>>> nil
>>>
>>
>>
>
--
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
