7

这是一段代码，它给了我一个StackOverflowError（从我的代码库中的一个实际示例归结为）：

( ->> (range 3000)
      (mapcat #(concat [0] (take 100 (repeat %))))
      (reduce (constantly nil))
      (count))

（注意：此代码仅用于演示问题或返回零。）

我可以通过以下任何步骤“拯救”它：

  1. 删除reduce线
  2. 更改[0]为 '(0)
  3. 在和(take 100000000)之间的任何点添加一个（或任何整数） 。mapcatcount

我基本上对这种行为感到困惑（尤其是＃2）。我会很感激任何意见。

（我觉得这可能与Why does reduce give a StackOverflowError in Clojure?有关，但我不太清楚如何 - 所以如果它是相关的，我会很感激解释原因。）

4

2 回答 2

10

在正常情况下，reduce使用loop/recur构造操作并使用常量堆栈空间。但是，您遇到了一个令人讨厌的极端情况，这是由于减少了通过提供concat交替的分块和非分块序列（向量[0]是分块的；产生的序列是非(take 100 (repeat %))分块的）而产生的序列。

当第一个参数concat是分块序列时，它将返回一个惰性序列，该序列将用于chunk-cons生成另一个分块序列。否则，它将cons用于生成非分块序列。

同时， 的实现reduce使用InternalReduce协议（定义在 中clojure.core.protocols），该协议internal-reduce为结构提供了一个函数，可以比默认的第一次/下一次递归更有效地减少自身。分块序列的internal-reduce实现使用分块函数在循环中消耗分块项目，直到它留下一个非分块序列，然后调用internal-reduce其余部分。默认internal-reduce实现类似地使用first/next在循环中使用项目，直到底层 seq 类型发生更改，然后调用internal-reduce新的 seq 类型以分派到适当的优化版本。随着您在生成的序列中前进concat，在分块和非分块子序列之间交替，internal-reduce调用堆积在堆栈上并最终炸毁它。

这种情况的一个更简单的说明是：

;; All chunked sub-seqs is OK
user> (reduce + (apply concat (take 10000 (repeat [1]))))
10000

;; All non-chunked sub-seqs is OK
user> (reduce + (apply concat (take 10000 (repeat '(1)))))
10000

;; Interleaved chunked and non-chunked sub-seqs blows the stack
user> (reduce + (apply concat (take 10000 (interleave (repeat [1]) (repeat '(1))))))
StackOverflowError   clojure.lang.LazySeq.seq (LazySeq.java:60)

检查堆栈跟踪：

StackOverflowError 
    clojure.core/seq (core.clj:133)
    clojure.core/interleave/fn--4525 (core.clj:3901)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.RT.seq (RT.java:484)
    clojure.core/seq (core.clj:133)
    clojure.core/take/fn--4232 (core.clj:2554)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.Cons.next (Cons.java:39)
    clojure.lang.RT.next (RT.java:598)
    clojure.core/next (core.clj:64)
    clojure.core/concat/cat--3925/fn--3926 (core.clj:694)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.ChunkedCons.chunkedNext (ChunkedCons.java:59)
    clojure.core/chunk-next (core.clj:660)
    clojure.core.protocols/fn--6041 (protocols.clj:101)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6034 (protocols.clj:147)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6041 (protocols.clj:104)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6034 (protocols.clj:147)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6041 (protocols.clj:104)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6034 (protocols.clj:147)
    clojure.core.protocols/fn--6005/G--6000--6014 (protocols.clj:19)
    clojure.core.protocols/fn--6041 (protocols.clj:104)

至于您的解决方法：

  • 显然，避免reduce完全避免了问题。
  • 更改[0]为'(0)用非分块子序列替换分块子序列，绕过对分块序列的优化，internal-reduce并允许减少发生在具有恒定堆栈空间的单个循环中。
  • 插入take创建一个新的、非分块的序列，完全由 cons 单元组成。
于 2014-10-16T16:39:07.093 回答
0

我认为问题在于mapcat，哪个调用concat，哪个使用cons。cons在向量上很昂贵（并且可能会消耗堆栈），而对于列表来说很便宜。这就是为什么从向量更改为列表“修复”问题的原因。

于 2014-10-16T08:00:56.413 回答