spec/valid 的评估时间？呈指数增长

Question

我正在使用 clojure.spec 来解析 DSL。不幸的是，测试是否符合我的规范的计算时间似乎呈指数级增长。我想了解原因以及解决方法。

规格如下：

(spec/def ::settings map?)

(spec/def ::header (spec/spec
                    (spec/cat :prefix #{:begin-example}
                              :label string?
                              :settings (spec/? ::settings))))

(def end-block [:end-example])

(spec/def ::not-end (partial not= end-block))

(spec/def ::end #{end-block})

(spec/def ::block (spec/cat
                   :header ::header
                   :data (spec/* ::not-end)
                   :suffix ::end))

(spec/def ::form (spec/alt :block ::block
                           :form any?))

(spec/def ::forms (spec/* ::form))

为了练习规范，我编写了一个小函数，为规范生成有效数据，以及一个控制数据大小的大小参数：

(defn make-sample-data [size]
  (transduce
   (comp (take size)
         cat)
   conj
   []
   (repeat [:a 1 :b :c [:begin-example "a" {:indent 4}] :d :e [:end-example] 9])))

(make-sample-data 1)
;; => [:a 1 :b :c [:begin-example "a" {:indent 4}] :d :e [:end-example] 9]

(make-sample-data 2)
;; => [:a 1 :b :c [:begin-example "a" {:indent 4}] :d :e [:end-example] 9 :a 1 :b :c [:begin-example "a" {:indent 4}] :d :e [:end-example] 9]

现在我正在执行这段代码：

(dotimes [i 13]
  (assert (time (spec/valid? ::forms (make-sample-data i)))))

产生以下输出：

"Elapsed time: 0.077095 msecs"
"Elapsed time: 0.333636 msecs"
"Elapsed time: 0.864481 msecs"
"Elapsed time: 2.198994 msecs"
"Elapsed time: 4.432004 msecs"
"Elapsed time: 9.026142 msecs"
"Elapsed time: 17.709151 msecs"
"Elapsed time: 35.201316 msecs"
"Elapsed time: 73.178516 msecs"
"Elapsed time: 138.93966 msecs"
"Elapsed time: 288.349616 msecs"
"Elapsed time: 569.471181 msecs"
"Elapsed time: 1162.944497 msecs"

在我看来，对于大小参数的每一步，计算时间都会加倍。

我的问题是：如何修改规范，使验证时间与数据大小呈线性关系？

Answer 1

我猜测性能问题来自贪婪、分支正则表达式规范与any?谓词的组合。

any? 在 s/alt :form 正则表达式分支中的使用对我来说很突出。我想规范可能正在评估 s/alt greedily/exhaustively 的每个分支，然后回溯，并且 any? 匹配所有包括匹配您的 [=16] 的值=] 分支。（请注意，无论 :form any? 分支是在 :block 分支之前还是之后定义的，规范都遵循相同的规范。）

如果您可以在顶级 s/alt :form 分支中使用比 any? 更具体的谓词，您应该会看到很大的改进。为了简洁起见，我内联了规范定义：

(s/def ::forms
  (s/*
    (s/alt :block
           (s/cat :header (s/spec
                            (s/cat :prefix #{:begin-example}
                                   :label string?
                                   :settings (s/? map?)))
                  :data (s/* #(not= % [:end-example]))
                  :suffix #{[:end-example]})
           :form
           (s/nonconforming ;; don't tag results
             (s/or :keyword keyword?
                   :number number?)))))

(time (s/valid? ::forms (make-sample-data 1000)))
"Elapsed time: 84.637513 msecs"
=> true

请注意，允许对 :form 分支使用集合谓词（例如 coll?、vector?）会降低性能，就像 any? 一样。我想这是因为相同的值匹配 s/alt.

的两个分支

spec/valid 的评估时间？呈指数增长

Evaluation time of spec/valid? grows exponentially

clojure

clojure.spec