On Wednesday, December 21, 2016 at 8:05:49 AM UTC-6, Przemysław Wojnowski wrote: > > Hello everybody, > > Recently I was implementing Insertion Sort in Clojure and did that using > transients: > --- cut --- > (defn- insert > "Insert element from `idx` into correct position in transient vector > `tv`." > [tv idx] > (let [current-value (get tv idx)] > (loop [i idx v tv] > (let [left-value (get v (dec i))] > (if (and (pos? i) > (> left-value current-value)) > (recur (dec i) (assoc! v i left-value)) > (assoc! v i current-value)))))) > > (defn insertion-sort > "Insertion sort using transients." > [v] > (let [size (-> v count dec)] > (loop [i 1 tv (transient v)] > (if (<= i size) > (recur (inc i) (insert tv i)) > (persistent! tv))))) > --- cut --- > > And have a few questions/concerns: > 1. IIUC transients are for this purpose - to do controlled performance > optimizations, right? >
Yes > 2. Imperative insertion sort has O(1) space requirement. Does transients > version have the same property? > Well, immutable data structures in general are trees, so they are probably more O(log n) space (for either persistent or transient). Transients batch up inserts but I'm not sure that really affects the overall space that much (the final structure is the same either way). > 3. I read that transients should not be bashed in place, but have seen the > following code, which seems to be only to be able to "bash in place": > (let [tv (atom (transient v))] > (doseq [exrps] > (reset! tv (assoc! tv k v))) > (persistent! tv)) > Is this approach idiomatic or should be avoided? To me it looks strange. > Here, the atom is being bashed in place, but the transient is not, so the code is ok in that respect (that is, the result of assoc! is replacing tv during the reset, not using the original value of tv). The atom is doing nothing of value here and just slowing things down though, so from that respect it seems wrong (seem to be some typos in there as well - the doseq is invalid and should be @tv on the last line, etc). > My approach is to write non-transient version, then just add transient, ! > to mutators, and persist result. > That is a good approach. > > Thank you, > Przemysław > -- 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/d/optout.
