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

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
`

由 Clojurians Slack 上的用户 @petrus 提供，由 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](https://clojure.atlassian.net/browse/CLJ-2327)（由gshayban报告）