为什么reduce给Clojure中的StackOverflowError？ [英] Why does reduce give a StackOverflowError in Clojure?

问题描述

我想连接Seq的Seq。

I'm trying to concatenate a Seq of Seqs.

我可以使用 apply concat 。

user=> (count (apply concat (repeat 3000 (repeat 3000 true))))
9000000

然而，从我有限的知识，我会假设使用 apply 强制惰性的Seq实现，这似乎不适合非常大的输入。我宁愿这样做，如果可以的话。

However, from my limited knowledge, I would assume that the use of apply forces the lazy Seq to be realised, and that doesn't seem right for very large inputs. I'd rather do this lazily if I can.

所以我以为使用 reduce 会做这项工作。

So I thought that using reduce would do the job.

user=> (count (reduce concat (repeat 3000 (repeat 3000 true))))

/ p>

But this results in

StackOverflowError   clojure.lang.RT.seq (RT.java:484)

我很惊讶，因为我会认为 reduce 的语义意味着它是tail-

I'm surprised because I would have thought that the semantics of reduce would mean it was tail-call recursive.

两个问题：

• 减少一般不适用于大输入？

• Is apply the best way to do this?
• Is reduce generally inappropriate for large inputs?

推荐答案

使用 apply 。当函数参数为lazy时， apply 。

子序列：

Use apply. When the function argument is lazy, so is apply.

Let's check that with a counting side effect on the underlying sub-sequences:

(def counter (atom 0))

(def ss (repeatedly 3000 
          (fn [] (repeatedly 3000 
            (fn [] (do (swap! counter inc) true))))))


(def foo (apply concat ss))

so.core=> @counter
0

so.core=> (dorun (take 1 foo))
nil

so.core=> @counter
1

so.core=> (dorun (take 3001 foo))
nil

so.core=> @counter
3001

---

reduce 与大量 concat 的溢出由于thunk组成

延迟序列，例如由 concat 产生的序列，使用thunk，延迟函数调用实现。当 concat 结果 concat 时，您已经在另一个thunk中嵌套了一个thunk。在你的函数中，嵌套深度为3000，因此一旦请求第一个项目和解开3000个嵌套thunk，堆栈就会溢出。

---

reduce with a large number of concats overflows due to thunk composition

Lazy sequences, such as those produced by concat are implemented with thunks, delayed function calls. When you concat the result of a concat you have nested a thunk within another thunk. In your function, the nesting goes 3000 deep and thus the stack is overflowed as soon as the first item is requested and the 3000 nested thunks are unwound.

so.core=>  (def bar (reduce concat (repeat 3000 (repeat 3000 true))))
#'so.core/bar

so.core=> (first bar)
StackOverflowError   clojure.lang.LazySeq.seq (LazySeq.java:49)

延迟序列的实现将一般解开嵌套thunk的蹦床风格 seq ed和不吹堆栈：

The implementation of lazy-sequences will in general unwind nested thunks trampoline style when seqed and not blow the stack:

so.core=> (loop [lz [1], n 0] 
            (if (< n 3000) (recur (lazy-seq lz) (inc n)) lz))
(1)

但是，如果在lazy-sequence中调用 seq 未实现的部分，同时实现它...

However, if you call seq within the lazy-sequence on the unrealized portion while realizing it...

so.core=> (loop [lz [1], n 0] 
            (if (< n 3000) (recur (lazy-seq (seq lz)) (inc n)) lz))
StackOverflowError   so.core/eval1405/fn--1406 (form-init584039696026177116.clj:1)

so.core=> (pst 3000)

StackOverflowError
        so.core/eval1619/fn--1620 (form-init584039696026177116.clj:2)
        clojure.lang.LazySeq.sval (LazySeq.java:40)
        clojure.lang.LazySeq.seq (LazySeq.java:49)
        clojure.lang.RT.seq (RT.java:484)
        clojure.core/seq (core.clj:133)
        so.core/eval1619/fn--1620 (form-init584039696026177116.clj:2)
        clojure.lang.LazySeq.sval (LazySeq.java:40)
        clojure.lang.LazySeq.seq (LazySeq.java:49)
        clojure.lang.RT.seq (RT.java:484)
        clojure.core/seq (core.clj:133)
        ... (repeatedly)

然后你最终构建 seq 堆栈帧。 concat 的实现是这样的。用 concat 检查StackOverflowError的堆栈跟踪，你会看到类似的。

Then you end up building seq stack frames. The implementation of concat is such. Examine the stack trace for your StackOverflowError with concat and you will see similar.

这篇关于为什么reduce给Clojure中的StackOverflowError？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！