Follow-up to "Simple String template replacement in Scala and Clojure"

In my previous post, I showed a simple (naive) algorithm for doing a String template replacement.

One of the solutions, provided by mikera, seems like a much better algorithm. I implemented it in Clojure (follows) and timed it against my previous algorithm. The new one is slower (41.475 msecs vs. 19.128 msecs) on 100 runs. I must be doing something stupid in my new implementation.

(defn replace-templates
  "Return a String with each occurrence of a substring of the form {key}
   replaced with the corresponding value from a map parameter.
   @param str the String in which to do the replacements
   @param m a map of keyword->value"
  [text m]
  (let [builder (StringBuilder.)
        text-length (.length text)]
    (loop [current-index 0]
      (if (>= current-index text-length)
        (.toString builder)
        (let [open-brace (.i开发者_如何学GondexOf text "{" current-index)]
          (if (< open-brace 0)
            (.toString (.append builder (.substring text current-index)))
            (let [close-brace (.indexOf text "}" open-brace)]
              (if (< close-brace 0)
                (.toString (.append builder (.substring text current-index)))
                (do
                  (.append builder (.substring text current-index open-brace))
                  (.append builder (let [key (keyword (.substring text (inc open-brace) close-brace))
                                         replacement (m key)]
                                     (if (nil? replacement) "" replacement)))
                  (recur (inc close-brace)))))))))))

although it passes all test cases:

(use 'clojure.test)

(deftest test-replace-templates
  (is (= (replace-templates "this is a test" {:foo "FOO"})
        "this is a test"))
  (is (= (replace-templates "this is a {foo} test" {:foo "FOO"})
        "this is a FOO test"))
  (is (= (replace-templates "this is a {foo} test {bar}" {:foo "FOO" :bar "BAR"})
        "this is a FOO test BAR"))
  (is (= (replace-templates "this is a {foo} test {bar} 42" {:foo "FOO" :bar "BAR"})
        "this is a FOO test BAR 42"))
  (is (= (replace-templates "this is a {foo} test {bar" {:foo "FOO" :bar "BAR"})
        "this is a FOO test {bar")))

; user=> Ran 1 tests containing 5 assertions.
; user=> 0 failures, 0 errors.
; user=> {:type :summary, :test 1, :pass 5, :fail 0, :error 0}

Here is the test code:

(time (dotimes [n 100] (replace-templates
  "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Pellentesque
elit nisi, egestas et tincidunt eget, {foo} mattis non erat. Aenean ut
elit in odio vehicula facilisis. Vestibulum quis elit vel nulla
interdum facilisis ut eu sapien. Nullam cursus fermentum
sollicitudin. Donec non congue augue. {bar} Vestibulum et magna quis
arcu ultricies consectetur auctor vitae urna. Fusce hendrerit
facilisis volutpat. Ut lectus augue, mattis {baz} venenatis {foo}
lobortis sed, varius eu massa. Ut sit amet nunc quis velit hendrerit
bibendum in eget nibh. Cras blandit nibh in odio suscipit eget aliquet
tortor placerat. In tempor ullamcorper mi. Quisque egestas, metus eu
venenatis pulvinar, sem urna blandit mi, in lobortis augue sem ut
dolor. Sed in {bar} neque sapien, vitae lacinia arcu. Phasellus mollis
blandit commodo." {:foo "HELLO" :bar "GOODBYE" :baz "FORTY-TWO"})))

; user=> "Elapsed time: 41.475 msecs"
; user=> nil

I wonder if the problem is the continuous reallocation of the StringBuilder.

I think you are hit by reflection. *warn-on-reflection* is your friend. Here some tests with criterium.

replace-templates-original:         56.4us
replace-templates-original-hinted:   9.4us
replace-templates-new:             131.4us
replace-templates-new-hinted:        6.3us
replace-templates-very-new:          7.3us

Here is the replace-templates-very-new, a version I did myself for golf. :)

(defn replace-templates-very-new
  [^String text m]
  (let [builder (StringBuilder.)]
    (loop [text text]
      (cond
        (zero? (count text))
        (.toString builder)

        (.startsWith text "{")
        (let [brace (.indexOf text "}")]
          (if (neg? brace)
            (.toString (.append builder text))
            (do
              (.append builder (get m (keyword (subs text 1 brace))))
              (recur (subs text (inc brace))))))

        :else
        (let [brace (.indexOf text "{")]
          (if (neg? brace)
            (.toString (.append builder text))
            (do
              (.append builder (subs text 0 brace))
              (recur (subs text brace)))))))))

It passes all tests, so it should work.

UPDATE: Support non-key brace enclosed values ("this is a {not-a-key-{foo}-in-the-map} test" => "this is a {not-a-key-FOO-in-the-map} test"), allowing it to be used in a Java code generator where non-key brace-enclosed things are significant :-).

(defn replace-templates-even-newer
  "Return a String with each occurrence of a substring of the form {key}
   replaced with the corresponding value from a map parameter.
   @param str the String in which to do the replacements
   @param m a map of keyword->value
   @thanks kotarak http://stackoverflow.com/questions/6112534/
     follow-up-to-simple-string-template-replacement-in-scala-and-clojure"
  [^String text m]
  (let [builder (StringBuilder.)]
    (loop [text text]
      (cond
        (zero? (count text))
        (.toString builder)

        (.startsWith text "{")
        (let [brace (.indexOf text "}")]
          (if (neg? brace)
            (.toString (.append builder text))
            (if-let [[_ replacement] (find m (keyword (subs text 1 brace)))]
              (do
                (.append builder replacement)
                (recur (subs text (inc brace))))
              (do
                (.append builder "{")
                (recur (subs text 1))))))

        :else
        (let [brace (.indexOf text "{")]
          (if (neg? brace)
            (.toString (.append builder text))
            (do
              (.append builder (subs text 0 brace))
              (recur (subs text brace)))))))))

I've written some Clojure code ( https://gist.github.com/3729307 ) that allows to interpolate any map value into a template, in probably the fastest possible way (see below) IF the template is known at compile-time.

It doesn't use the same template syntax (although it could be adapted for that), but I think it still can be used to solve the exact same problem.

With this solution, the code would have to be rewritten like...

; renderer-fn is defined in https://gist.github.com/3729307
(time (dotimes [n 100] ((renderer-fn
"Lorem ipsum dolor sit amet, consectetur adipiscing elit. Pellentesque
elit nisi, egestas et tincidunt eget, " (:foo %) " mattis non erat. Aenean ut
elit in odio vehicula facilisis. Vestibulum quis elit vel nulla
interdum facilisis ut eu sapien. Nullam cursus fermentum
sollicitudin. Donec non congue augue. " (:bar %) " Vestibulum et magna quis
arcu ultricies consectetur auctor vitae urna. Fusce hendrerit
facilisis volutpat. Ut lectus augue, mattis " (:baz %) " venenatis " (:foo %)
"lobortis sed, varius eu massa. Ut sit amet nunc quis velit hendrerit
bibendum in eget nibh. Cras blandit nibh in odio suscipit eget aliquet
tortor placerat. In tempor ullamcorper mi. Quisque egestas, metus eu
venenatis pulvinar, sem urna blandit mi, in lobortis augue sem ut
dolor. Sed in " (:bar %) " neque sapien, vitae lacinia arcu. Phasellus mollis
blandit commodo.") {:foo "HELLO" :bar "GOODBYE" :baz "FORTY-TWO"})))

; => "Elapsed time: 1.371 msecs"

To be honest, your solution looks more like Java in Clojure clothing. Clojure already has the quite flexible clojure.string/replace function which is able to do what you need. Also, your docstring is not matching the Clojure conventions. I would suggest something like this:

(defn replace-templates
  "Returns a string with each occurrence of the form `{key}` in a
  `template` replaced with the corresponding value from a map
  `m`. Keys of `m` are expected to be keywords."
  [template m]
  (clojure.string/replace template #"\{([^{]+?)\}"
    (fn [[orig key]] (or (get m (keyword key)) orig))))

As one can imagine, replace is already quite optimized, so there is no real reason to roll an own implementation. It's using StringBuffer internally, while you're using StringBuilder, so your implementation might save a few microseconds -- nothing worth talking about.

If you really care about every microsecond you probably should look into the macro approach. If that is not possible because e.g. you're loading the template from a file then i/o will be a bigger concern anyway. Also in this case I would suggest looking into the Selmer template system, which has a slightly different syntax (with double instead of single curly braces for replacements) but is also much more flexible in what it can do.