It would be great if you people could help me with the optimization .. just few tricks and it may work.. or guide me towards the resources..
On Monday, 13 October 2014 18:40:15 UTC+5:30, Ashish Negi wrote: > > I am competing in an online competition and the scenario is like this : > I coded with my basic knowledge of clojure and got 11 out of 20 testcases > and others being timed out and one being runtime error.. > > I started optimizing my code and read > https://groups.google.com/forum/#!searchin/clojure/performance/clojure/SxT2MaOsip8/xoMkDVHeOqMJ > and other google articles for performance.. but after that i just managed > to solve only one more problem and i am stuck at 12 solved.. ( the time for > each case is 8 seconds max) > The last 12th was completed in 7.05 secs :) .. just on the border huh... :) > > The problem is about that of Solving calculataor expressions like > "2+3/2/2/(2+8)" mod 10^8+7 gives answer 10^8+3.. > Nevertheless it is the concern but optimizing code is :) > > This is current condition of my code : > > (ns fpcontest.expression) > > (def Term) > (def Factor) > > (def ToMod (int (+ 1000000000 7))) > > ;; (int ToMod) > > (def toPrint false) > > (defn myprintln [& args] > ;; (if toPrint > ;; (apply println args)) > ) > > (defn EulerDivNonMemo [^long x ^long p] > (let [ToMod (+ p 2)] > (loop [num (long 1) toPow p numDouble x] > (if (= 0 toPow) > ;;(do (myprintln " EulerDiv : " num " for " x p)) > num > (let [numDouble2 (rem (* numDouble numDouble) ToMod) > halfToPow (bit-shift-right toPow 1)] > (if (odd? toPow) > (recur (rem (* num numDouble) ToMod) > halfToPow > numDouble2) > (recur num halfToPow numDouble2)) > > )))) > ) > > (def EulerDiv (memoize EulerDivNonMemo) > ) > > ;; (EulerDiv 2 2) > ;; (defn TestEulerDiv [] > ;; (and > ;; (= 2 (mod (* 4 (EulerDiv 2 (- 3 2))) 3)) > ;; (= 1 (mod (* 2 (EulerDiv 2 (- 3 2))) 3)) > ;; (= 1 (int (mod (* 2 (EulerDiv 2 (- ToMod 2))) ToMod)))) > ;; ) > > ;; (= true (TestEulerDiv)) > > (defn Expression [lst] > (let [term (Term lst) > ;; p (myprintln term " term for exp " lst) > sizeTerm (count term) > evaluateExpr > (fn [opr lst] > (let [expr (Expression (drop 2 lst)) > ;; p (myprintln expr " expr for Expr " lst " and " opr) > intLst (first lst)] > (cons (rem (opr intLst > (first expr)) > ToMod) (drop 1 expr))))] > (if (> sizeTerm 2) > (if (= (second term) "+") > (evaluateExpr + term) > (if (= (second term) "-") > (evaluateExpr - term) > term) > ) > ;; first of term is the answer > term > ) > )) > > > (defn Term [lst] > (let [factor (Factor lst) > ;; p (myprintln factor " factor for term " lst) > sizeFactor (count factor) > evaluateExpr > (fn [opr lst] > (let [expr (Term (drop 2 lst)) > ;;p (myprintln expr " term for expr " > lst " and " opr) > intLst (first lst)] > (cons (rem (opr intLst > (first expr)) > ToMod) (drop 1 expr) )))] > (if (> sizeFactor 2) > (if (= (second factor) "*") > (evaluateExpr * factor) > (if (= (second factor) "/") > (let [expr (Term (drop 2 factor)) > fExpr (first expr)] > (cons (rem (* (first factor) (EulerDiv fExpr (- ToMod 2))) > ToMod) (drop 1 expr)) > ) > ;;(evaluateExpr / factor) > factor) > ) > factor > ) > )) > > (defn Factor [lst] > (let [fFactor (first lst) > ;;p (myprintln " Factor has : " lst) > ] > (if (= fFactor "+") > (cons (int (Integer. (second lst))) (rest lst)) > (if (= fFactor "-") > (cons (- (int (Integer. (second lst)))) (rest (rest lst))) > (if (= fFactor "(") > ;; remove the '(' and ')' > (let [expr (Expression (rest lst))] > (cons (first expr) (drop 2 expr)) > ) > ;; (if (= (count lst) 1)) > (cons (int (Integer. (first lst))) (rest lst)) > ;;(myprintln "I do not know where i am... " lst) > > ) > )) > ) > > (defn split-with-delim [d s] > (clojure.string/split > s (re-pattern (str "(?=" d > ")|(?<=" d > ")")))) > > (defn make-calulator-list [s] > (->> s > (split-with-delim #"[\/\+\-\*\(\) ]") > (filter #(not (or (= "" %) (= " " %)))) > doall > )) > > (defn StartRun [FuncToCall inputParse outputParse] > (let [lines (line-seq (java.io.BufferedReader. *in*))] > (outputParse (FuncToCall (inputParse (first lines))))) > ) > > > and this is how i am testing my code ................................ > ****************** Test ******************************** > > > > > (defn RunTests [] > (and > (= 1717 (int (first (Expression (make-calulator-list " 22 * 79 - > 21"))))) > > (= 12 (int (first (Expression (make-calulator-list " 4/2/2 + 8"))))) > > (= 4 (int (first (Expression (make-calulator-list "4/-2/2 + 8"))))) > > (= 999998605 (int (mod (first (Expression (make-calulator-list > "55+3-45*33-25"))) ToMod))) > > (= 999999987 (int (mod (first (Expression (make-calulator-list > "4/-2/(2+8)"))) ToMod))) > > (= 22 (int (first (Expression (make-calulator-list "(22)*+1/-1+(1)"))))) > > (= 22 (int (first (Expression (make-calulator-list "11*(2/2)*2"))))) > > (= 11 (int (first (Expression (make-calulator-list "22*2/2*2"))))) > > (= '("4" "/" "-" "2" "/" "2" "+" "8") > (make-calulator-list "4/-2/2 + 8")) > (= '("4" "/" "-" "2" "/" "(" "2" "+" "8" ")") > (make-calulator-list " 4/-2/(2 + 8)")) > > ) > ) > > (RunTests) > > (Expression '("3" "+" "2")) > > (conj '("3") 1) > (cons 2333 '(2 3 4)) > (cons 2 (drop 1 '())) > (drop 1 '()) > > (str (int 1.0)) > (cons "1" '(1 "3")) > (cons "1" nil) > (int (Integer. "1")) > > (int (mod (first (Expression (make-calulator-list "4/-2/(2+8)"))) ToMod)) > > > (mod (first (Expression (make-calulator-list "4/2"))) ToMod) > > > (defn diffTime [func & args] > (let [start (.getTime (java.util.Date.)) > res (apply func args) > end (.getTime (java.util.Date.))] > (- end start))) > > (defn somuchtime= [times] > (let [start (java.util.Date.) > ] > (loop [iTime 0] > (if (= iTime times) > start > (recur (inc iTime)))))) > > > (defn GenerateCalculatorTests [nums] > (loop [num 0 sb (StringBuilder.)] > (if (= num nums) > (str "1" (.toString sb)) > (->> sb > ((fn [sb] > (let [r (rand-int 500)] > (do (if (< r 100) > (.append sb "+") > (if (< r 200) > (.append sb "-") > (if (< r 300) > (.append sb "*") > (if (< r 497) > (.append sb "/") > (.append sb (str > "*(" > (GenerateCalculatorTests 4) > ")+")))))) > (.append sb (rand-int 1000000000)) > sb)))) > (recur (inc num)) > )) > ) > ) > > (GenerateCalculatorTests 50) > > (defn Execute [num] > (let [str (GenerateCalculatorTests num)] > (do (println str " = " ) (Expression (make-calulator-list > (GenerateCalculatorTests num)))))) > > (diffTime Execute 2074) > > > > I find that the last problem which is giving runtime error is may be > StackOverflow as i get it in with > (diffTime Execute 3000) ;; where 3000 tries to get a calculator expression > of 3000 or more ints.. see GenerateCalculatorTests.. > > > with diffTime i also found that using rem is faster than using mod.. > -- 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 --- 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
