On Sun, Jul 25, 2010 at 00:16, samnardoni <samnard...@googlemail.com> wrote: > I have a simple string (or list of characters to be precise) in a form > of: "1234<5678<<9". > > I want to parse this string and end up with: "123569". > > The "<" is essentially the same as a "backspace". > > I managed to implement this fairly simply using the reduce function - > source: http://gist.github.com/489019. >
Yes, that's a good use of reduce. If you really need performance, however, you might consider dropping down more imperative in this case. I was able to cut the runtime to about 10% by reformulating the problem in terms of String and StringBuilder. The necessary code, though, is really ugly: (ns backspace) (def data-with-deletions (apply str (repeat 10000 (str "12345<<789<ABC<<<DE<FGHIJKLMNOPQRSTUVWXYZ<<0123456" "00000000000000000000000000000000000000000000000000")))) (def data-without-deletions (apply str (repeat 1000000 "0"))) (defn run-program [program] (letfn [(step [stack char] (if (= char \<) (pop stack) (conj stack char)))] (reduce step [] program))) (defn time-run-program [data] (count (time (run-program data)))) (defn run-program2 [^String program] (loop [i 0, j (.indexOf program "<"), b (StringBuilder.)] (if (= -1 j) (.toString (.append b (.substring program i))) (let [k (int (loop [k (inc j)] (if (= (.charAt program k) \<) (recur (inc k)) k)))] (recur (int k) (.indexOf program "<" k) (.append b (.substring program i (- j (- k j))))))))) (defn time-run-program2 [data] (count (time (run-program2 data)))) (defn timings [] (println "run-program on data without deletions") (dorun (repeatedly 10 #(time-run-program data-without-deletions))) (println "run-program on data with deletions") (dorun (repeatedly 10 #(time-run-program data-with-deletions))) (println "run-program2 on data without deletions") (dorun (repeatedly 10 #(time-run-program2 data-without-deletions))) (println "run-program2 on data with deletions") (dorun (repeatedly 10 #(time-run-program2 data-with-deletions)))) ;; --------------------------------------------------------------------------- ;; On a 1.6Ghz Atom (Dell Mini 9) ;; --------------------------------------------------------------------------- ;; run-program on data without deletions ;; "Elapsed time: 1658.232133 msecs" ;; "Elapsed time: 883.943424 msecs" ;; "Elapsed time: 865.990504 msecs" ;; "Elapsed time: 840.566116 msecs" ;; "Elapsed time: 816.676015 msecs" ;; "Elapsed time: 815.181318 msecs" ;; "Elapsed time: 808.408751 msecs" ;; "Elapsed time: 811.207018 msecs" ;; "Elapsed time: 828.006483 msecs" ;; "Elapsed time: 805.052535 msecs" ;; run-program on data with deletions ;; "Elapsed time: 805.520812 msecs" ;; "Elapsed time: 763.458827 msecs" ;; "Elapsed time: 786.309237 msecs" ;; "Elapsed time: 784.190927 msecs" ;; "Elapsed time: 779.576116 msecs" ;; "Elapsed time: 776.683829 msecs" ;; "Elapsed time: 788.427932 msecs" ;; "Elapsed time: 766.683824 msecs" ;; "Elapsed time: 762.674231 msecs" ;; "Elapsed time: 759.6923 msecs" ;; run-program2 on data without deletions ;; "Elapsed time: 16.040587 msecs" ;; "Elapsed time: 17.901927 msecs" ;; "Elapsed time: 30.643421 msecs" ;; "Elapsed time: 32.301243 msecs" ;; "Elapsed time: 19.36524 msecs" ;; "Elapsed time: 16.757645 msecs" ;; "Elapsed time: 15.305436 msecs" ;; "Elapsed time: 23.4835 msecs" ;; "Elapsed time: 30.554508 msecs" ;; "Elapsed time: 25.414402 msecs" ;; run-program2 on data with deletions ;; "Elapsed time: 324.703781 msecs" ;; "Elapsed time: 73.732552 msecs" ;; "Elapsed time: 95.258957 msecs" ;; "Elapsed time: 92.265781 msecs" ;; "Elapsed time: 69.199159 msecs" ;; "Elapsed time: 77.407051 msecs" ;; "Elapsed time: 62.621647 msecs" ;; "Elapsed time: 78.062991 msecs" ;; "Elapsed time: 68.359239 msecs" ;; "Elapsed time: 58.825144 msecs" -- 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
