正则表达式规范似乎表现出指数级内存消耗

Question

此示例代码在不太长输入的情况下将引发内存溢出，并且似乎在此时减速呈现指数级增长。如果不是错误，那它对测试套件来说是一个有用的示例。

`
(s/def ::thing
(s/+ (s/alt :x (s/+ (set (range 70))))))

(time (s/conform ::thing (range 10))) ;; 30ms
(time (s/conform ::thing (range 15))) ;; 500ms
(time (s/conform ::thing (range 20))) ;; 24s
`

摘录自用户 @petrus 在 Clojurians Slack 中的内容，由 Max Penet 简化。

Answer 1

评论由：mpenet 发表

可以将示例简化为

`
(s/def ::thing
(s/+ (s/alt :x (s/+ (set (range 70))))))

(time (s/conform ::thing (range 10))) ;; 30ms
(time (s/conform ::thing (range 15))) ;; 500ms
(time (s/conform ::thing (range 20))) ;; 24s
`

Answer 2

评论由：gshayban 发表

感谢 Max 的简化！

Answer 3

参考： https://clojure.atlassian.net/browse/CLJ-2327 (由 gshayban 报告)