On Jul 21, 12:15 pm, Tassilo Horn <tass...@member.fsf.org> wrote:
> Hi all,
>
> probably I don't see the forest for trees, but anyhow. In my graph
> transformation lib I have these functions for applying rules:
>
> --8<---------------cut here---------------start------------->8---
> (defn iteratively
> "Applies the function f with args as long as it returns logical true.
> Returns the number of successful applications or nil if it couldn't be
> applied at least once."
> [r & args]
> (loop [val (apply r args), i 0]
> (if val
> (recur (apply r args) (inc i))
> (if (zero? i) nil i))))
>
> (defn choose
> "Chooses non-deterministically one of the given funs and applies it.
> Returns the value of applying the chosen fun.
> Returns nil if none of the funs was applicable."
> [& funs]
> (when (seq funs)
> (let [fun (rand-nth funs)
> val (fun)]
> (or val (recur (remove #(= fun %) funs))))))
>
> (defn fold-constants
> [g]
> (let [start-block (the (vseq g 'StartBlock))]
> (iteratively pull-up-consts g)
> (iteratively replace-not g start-block)
> (iteratively replace-binary g start-block)))
>
> (defn fold-constants-with-choose
> [g]
> (let [start-block (the (vseq g 'StartBlock))]
> (iteratively (fn []
> (choose #(pull-up-consts g)
> #(replace-not g start-block)
> #(replace-binary g start-block))))))
>
> ;; Takes 3.5 secs
> (time (fold-constants g))
>
> ;; Takes 450 times longer!
> (time (fold-constants-with-choose g))
> --8<---------------cut here---------------end--------------->8---
>
> Why does the variant with `choose' take 450 times longer than without?
> The individual rules match totally disjunctive structures and there's a
> fixed number of places where a rule can be applied. So even if choose
> always selects the single applicable rule at last I wouldn't expect a
> slowdown of more than 3.
>
> Any hints?
(1) The first version is doing way less work. It tries the first rule
until it runs out of steam, then the second rule, then the third rule.
If the third rule produces a structure that the first rule could have
matched, it will never be tried, because the first rule is done. The
second version, however, keeps reducing the structure using all three
rules until there are no transformation available.
(2) Your implementation of choose is pretty inefficient itself. rand-
nth is slow, remove is slow...If you're using it in a performance-
sensitive area, I would write it differently. Especially, you could
probably gain a lot by making choose return a function, rather than
immediately execute something, so that it can pre-compute the data
that it will use more than once. Something like this (untested):
(defn choose
"Chooses non-deterministically one of the given funs and applies
it.
Returns the value of applying the chosen fun.
Returns nil if none of the funs was applicable."
[& funs]
(let [fnmap (vec funs)]
(fn []
(loop [fns fnmap, tries-left (count fns)]
(when-not (zero? tries-left)
(let [idx (rand-int tries-left)
f (get fns idx)
val (f)]
(or val (recur (assoc fns idx
(get fns (dec tries-left)))
(dec tries-left)))))))))
(defn fold-constants-with-choose
[g]
(let [start-block (the (vseq g 'StartBlock))]
(iteratively (choose #(pull-up-consts g)
#(replace-not g start-block)
#(replace-binary g start-block)))))
--
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
