“Scala 和 Clojure 中的简单字符串模板替换”的后续内容

Question

在我之前的帖子中，我展示了一个简单的（天真的）进行字符串模板替换的算法。

mikera 提供的解决方案之一似乎是一种更好的算法。我在 Clojure 中实现了它（如下），并根据我之前的算法对其进行了计时。新的在 100 次运行中较慢（41.475 毫秒 vs. 19.128 毫秒）。我一定在我的新实现中做了一些愚蠢的事情。

(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 (.indexOf 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)))))))))))

虽然它通过了所有测试用例：

(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}

这是测试代码：

(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

我想知道问题是否是 StringBuilder 的连续重新分配。

Answer 1

我认为你受到了反思的打击。 *warn-on-reflection* 是你的朋友。这里是一些使用标准的测试。

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

这是replace-templates-very-new，这是我自己为高尔夫制作的一个版本。 :)

(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)))))))))

它通过了所有测试，所以它应该可以工作。

更新：支持非键大括号括起来的值（“这是一个 {not-a-key-{foo}-in-the-map} 测试”=>“这是一个{not-a-key-FOO-in-the-map} test")，允许它在 Java 代码生成器中使用，其中非键大括号括起来的内容很重要:-)。

(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)))))))))

Answer 2

我编写了一些 Clojure 代码（ https://gist.github.com/3729307 ），允许将任何映射值插入到模板中，可能是最快的方式（见下文）如果模板在编译时已知。

它不使用相同的模板语法（尽管它可以适应这一点），但我认为它仍然可以用来解决完全相同的问题。

使用这个解决方案，代码必须像这样重写......

; 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"

Answer 3

老实说，您的解决方案看起来更像是披着 Clojure 外衣的 Java。 Clojure 已经有了相当灵活的 clojure.string /replace 函数可以满足您的需要。另外，您的文档字符串与 Clojure 约定不匹配。我建议这样：

(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))))

正如人们可以想象的那样，替换已经相当优化，因此没有真正的理由推出自己的实现。它在内部使用 StringBuffer，而您使用 StringBuilder，因此您的实现可能会节省几微秒——没什么值得谈论的。

如果您真的关心每一微秒，您可能应该研究宏观方法。如果这是不可能的，因为例如您正在从文件加载模板，那么 I/O 无论如何都会成为一个更大的问题。同样在这种情况下，我建议查看 Selmer 模板系统，它的语法略有不同（双花括号而不是单花括号进行替换），但它的功能也更加灵活。