Время оценки спецификации / действителен?растет в геометрической прогрессии - PullRequest
Новая
       36

Время оценки спецификации / действителен?растет в геометрической прогрессии

0 голосов
/ 31 января 2019

Я использую 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"

Мне кажется, что для каждого шага параметра размера время вычисления удваивается.

Мой вопрос: Как я могу изменить мою спецификацию так, чтобы время проверки было линейным с размером моих данных?

1 Ответ

0 голосов
/ 31 января 2019

Я догадываюсь проблема производительности возникает из-за сочетания жадных, ветвящихся спецификаций регулярных выражений с предикатами any?.

Использование any? в регулярном выражении s/alt :formфилиал выделился мне.Я полагаю, что spec может жадно / исчерпывающе оценивать каждую ветвь s/alt, а затем возвращаться назад, и any? соответствует всему , включая значения, которые соответствуют вашей :block ветви.(Обратите внимание, что спецификация совпадает независимо от того, определена ли ветвь :form any? до или после ветки :block.)

Если вы можете использовать более конкретный предикат, чем any? в вашем верхнем уровне s/alt :form ветка, вы должны увидеть большое улучшение.Я кратко описал определения спецификаций для краткости: 

(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

Обратите внимание, что разрешение предиката коллекции (например, coll?, vector?) для этой ветви :form снижает производительность точно так же, как any?.Я полагаю, это потому, что одинаковые значения соответствуют обеим ветвям s/alt.

...