Sorry but I don't feel that I'm understanding your code enough to rewrite it (for instance, why substract 2 at https://gist.github.com/ashishnegi/a9ae3fb3c270c7d3742e#file-calculator-clj-L102 to add 2 at https://gist.github.com/ashishnegi/a9ae3fb3c270c7d3742e#file-calculator-clj-L16 ?). But if I was to write it, I'd use a library to parse the expressions (see https://github.com/Engelberg/instaparse ). If you really want to do it yourself, the lexing step (
make-calulator-list)shouldn't return strings but numbers and keywords for operations imo. And from the list you could build an Abstract Syntax Tree either with nested vectors or if speed is of essence with records (or maybe looking into https://github.com/ztellman/clj-tuple ). Processing the AST should be then much simpler than processing your strings list. Try to avoid recursion if possible by expressing your proccessing with reduce for instance. BTW, are you sure than int is a large enough type ? I'd use long and check that the mod is small enough. My two cents. On Monday, October 13, 2014 3:10:15 PM UTC+2, 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.
