में एएसटी (अमूर्त वाक्यविन्यास पेड़) का मूल्यांकन करना बेहतर प्रदर्शन के साथ एएसटी का मूल्यांकन कैसे करें? वर्तमान में हम एएसटी को पेड़ के रूप में बनाते हैं जहां पत्ता नोड्स (टर्मिनल) एक तर्क के कार्य होते हैं - कीवर्ड का मानचित्र और उनके मूल्य। टर्मिनलों को कीवर्ड के साथ दर्शाया जाता है, और फ़ंक्शन (गैर टर्मिनल) उपयोगकर्ता (या क्लोजर) परिभाषित फ़ंक्शंस हो सकते हैं।क्लोजर
(defn full-growth
"Creates individual by full growth method: root and intermediate nodes are
randomly selected from non-terminals Ns,
leaves at depth depth are randomly selected from terminals Ts"
[Ns Ts arity-fn depth]
(if (<= depth 0)
(rand-nth Ts)
(let [n (rand-nth Ns)]
(cons n (repeatedly (arity-fn n) #(full-growth Ns Ts arity-fn(dec depth)))))))
उत्पन्न एएसटी का उदाहरण:: पूर्ण विकास पद्धति गैर टर्मिनल और टर्मिनल से पेड़ बनाता
=> (def ast (full-growth [+ *] [:x] {+ 2, * 2} 3))
#'gpr.symb-reg/ast
=> ast
(#object[clojure.core$_STAR_ 0x6fc90beb "[email protected]"]
(#object[clojure.core$_STAR_ 0x6fc90beb "[email protected]"]
(#object[clojure.core$_STAR_ 0x6fc90beb "[email protected]"]
:x
:x)
(#object[clojure.core$_PLUS_ 0x1b00ba1a "[email protected]"]
:x
:x))
(#object[clojure.core$_PLUS_ 0x1b00ba1a "[email protected]"]
(#object[clojure.core$_PLUS_ 0x1b00ba1a "[email protected]"]
:x
:x)
(#object[clojure.core$_PLUS_ 0x1b00ba1a "[email protected]"]
:x
:x)))
, जो
`(~* (~* (~* ~:x ~:x) (~+ ~:x ~:x)) (~+ (~+ ~:x ~:x) (~+ ~:x ~:x)))
(def ast `(~* (~* (~* ~:x ~:x) (~+ ~:x ~:x)) (~+ (~+ ~:x ~:x) (~+ ~:x ~:x))))
के बराबर हम fn जो सीधे मूल्यांकन करता है लिख सकते हैं इस एएसटी के रूप में:
(defn ast-fn
[{x :x}]
(* (* (* x x) (+ x x)) (+ (+ x x) (+ x x))))
=> (ast-fn {:x 3})
648
हम समारोह बनाने के लिए दो तरीकों एएसटी पर आधारित है, लागू करते हैं और नक्शे की मदद से एक है, और की मदद से अन्य कंप्यूटर अनुप्रयोग और juxt:
(defn tree-apply
"((+ :x :x) in) => (apply + [(:x in) (:x in))]"
([tree] (fn [in] (tree-apply tree in)))
([tree in]
(if (sequential? tree)
(apply (first tree) (map #(tree-apply % in) (rest tree)))
(tree in))))
#'gpr.symb-reg/tree-apply
=> (defn tree-comp
"(+ :x :x) => (comp (partial apply +) (juxt :x :x))"
[tree]
(if (sequential? tree)
(comp (partial apply (first tree)) (apply juxt (map tree-comp (rest tree))))
tree))
#'gpr.symb-reg/tree-comp
=> ((tree-apply ast) {:x 3})
648
=> ((tree-comp ast) {:x 3})
648
समय के साथ fn हम परीक्षण मामलों से अधिक कार्यों को क्रियान्वित करने के लिए समय को मापने:
=> (defn timing
[f interval]
(let [values (into [] (map (fn[x] {:x x})) interval)]
(time (into [] (map f) values)))
true)
=> (timing ast-fn (range -10 10 0.0001))
"Elapsed time: 37.184583 msecs"
true
=> (timing (tree-comp ast) (range -10 10 0.0001))
"Elapsed time: 328.961435 msecs"
true
=> (timing (tree-apply ast) (range -10 10 0.0001))
"Elapsed time: 829.483138 msecs"
true
आप देख सकते हैं वहाँ प्रत्यक्ष समारोह (ast-fn) के बीच प्रदर्शन में बड़ा अंतर है, पेड़ कम्पास समारोह और पेड़ों पर लागू उत्पन्न समारोह उत्पन्न।
क्या कोई बेहतर तरीका है?
संपादित करें: पागलपन का जवाब काफी आशाजनक दिखता है। मैं (निरंतर समारोह जो लगातार मान देता है, इनपुट की परवाह किए बिना की तरह बस कीवर्ड टर्मिनल भी कुछ अन्य काम करता है, नहीं हो सकता है,) उसके समाधान पर कुछ सुधार किए हैं:
(defn c [v] (fn [_] v))
(def c1 (c 1))
(defmacro full-growth-macro
"Creates individual by full growth method: root and intermediate nodes are
randomly selected from non-terminals Ns,
leaves at depth depth are randomly selected from terminals Ts"
[Ns Ts arity-fn depth]
(let [tree (full-growth Ns Ts arity-fn depth)
val-map (gensym)
ast2f (fn ast2f [ast] (if (sequential? ast)
(list* (first ast) (map #(ast2f %1) (rest ast)))
(list ast val-map)))
new-tree (ast2f tree)]
`{:ast '~tree
:fn (fn [~val-map] ~new-tree)}))
, के उपयोग के साथ बिताए-मीटर (बनाने टर्मिनल के रूप में निरंतर C1) और संबद्ध ast-एम-fn:
समय बहुत जैसा दिखता है:
=> (timing (:fn ast-m) (range -10 10 0.0001))
"Elapsed time: 58.478611 msecs"
true
=> (timing (:fn ast-m) (range -10 10 0.0001))
"Elapsed time: 53.495922 msecs"
true
=> (timing ast-m-fn (range -10 10 0.0001))
"Elapsed time: 74.412357 msecs"
true
=> (timing ast-m-fn (range -10 10 0.0001))
"Elapsed time: 59.556227 msecs"
true
मेरा उत्तर शायद बहुत मदद नहीं कर सकता है, क्योंकि आप शायद रनटाइम पर सबकुछ करना चाहते हैं, लेकिन इससे मुझे मैक्रोज़ काम करने के तरीके को बेहतर बनाने में मदद मिली। तो धन्यवाद। +1 – madstap