Thanks juan
I thought that people would prefer the code.. and just wanted to have them
glanced at it.. and tell if i am missing something basic.
But here is a little list of things i tried :
The problem is that of evaluation calculator expressions containig *,/,+,-
and (, )
and the grammar for this is right associative for operators and precendence
is as we know : -> unaray, () > */ > +-
So i think i have implemented recursive descend parser for this ;
This is the general thing about the problem
And from optimization point of view :
The length of the input string would be 10^5 which means that worst case it
would take 10^4 numbers
and doing this in repl shows :
user> (time (dotimes [_ 10]
((fn [times]
(reduce (fn [x y] (rem (* x y) 1000000007))
1 (map inc (range times)))
)
10000)
))
"Elapsed time: 35.591417 msecs"
so i think that computing numbers would not be a pain point for me..
so then another problem i think may be is..
with regex that is used for splitting the input string :
(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
))
Doing in REPL :
(time (dotimes [_ 10] (println (count (time (make-calulator-list (time
(GenerateCalculatorTests 2000))
))))))
** Input Format : first line - time taken in generating the string , second
line - regex splitting and third line length of list returned after
splitting..
"Elapsed time: 289.126875 msecs"
"Elapsed time: 294.026862 msecs"
4121
"Elapsed time: 369.041191 msecs"
"Elapsed time: 372.199697 msecs"
4121
"Elapsed time: 365.559413 msecs"
"Elapsed time: 368.797257 msecs"
4205
"Elapsed time: 289.313576 msecs"
"Elapsed time: 292.487476 msecs"
4157
"Elapsed time: 310.207399 msecs"
"Elapsed time: 313.748384 msecs"
4277
"Elapsed time: 295.76637 msecs"
"Elapsed time: 300.253091 msecs"
4109
"Elapsed time: 302.364814 msecs"
"Elapsed time: 307.980419 msecs"
4145
"Elapsed time: 299.220518 msecs"
"Elapsed time: 302.353367 msecs"
4085
"Elapsed time: 292.046185 msecs"
"Elapsed time: 295.306528 msecs"
4181
"Elapsed time: 289.706317 msecs"
"Elapsed time: 292.845481 msecs"
4133
"Elapsed time: 3149.529342 msecs"
Which shows that since input string is given to me : ( I am generating it
randomly here ) , so time is around 3 msecs which can also not be a
bottleneck..
and then their is EulerDivMod which is
(time (dotimes [_ 1000]
(EulerDivNonMemo 2 (- ToMod 2))))
"Elapsed time: 21.902319 msecs"
which is also not a bottleneck..
So now i have only My recursive descend parser which is in Function
Expression, Term and Factor which are not doing computationally big things
like * or / but what are they doing may be wrong like
-->> I take the list and it flows back and forth between the Expression ->
Term <-> Factor <-> Expression and so on..
In each function call of above i change the incoming list (creating new one
cons) and return that..
but
(time (dotimes [_ 10]
(time (Expression (make-calulator-list
(time (GenerateCalculatorTests 2000)))))))
"Elapsed time: 296.071484 msecs"
"Elapsed time: 706.866377 msecs"
"Elapsed time: 286.394266 msecs"
"Elapsed time: 681.03349 msecs"
"Elapsed time: 284.475953 msecs"
"Elapsed time: 676.624133 msecs"
"Elapsed time: 280.001073 msecs"
"Elapsed time: 666.90468 msecs"
"Elapsed time: 283.980191 msecs"
"Elapsed time: 676.609133 msecs"
"Elapsed time: 284.706861 msecs"
"Elapsed time: 684.848012 msecs"
"Elapsed time: 281.24995 msecs"
"Elapsed time: 666.264847 msecs"
"Elapsed time: 297.805466 msecs"
"Elapsed time: 691.719993 msecs"
"Elapsed time: 281.54125 msecs"
"Elapsed time: 684.12371 msecs"
"Elapsed time: 281.470597 msecs"
"Elapsed time: 672.724747 msecs"
"Elapsed time: 6811.717182 msecs"
so it seems it is also taking 400 msecs around for input of size 2000
whereas maximum can be of 10000 like 5 times..
but for that input i go StackOverflow..
however the online judge is showing Timeout for some problems and Runtime
for 1 problem so i guess i am getting input within my range..
but what can be the problem then ?
I also tried adding "doall" in my make-calulator-list ..
Also, I tried using transients in Expression, Term and Factor..
however, i could not find transients for lists... I found for vector ?
Should i use vector ? would that make it faster ? and then use transients..
?
--
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.
