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
