reduce 和 map 累加器产生堆栈溢出

Question

为什么我需要在这段代码中将map替换为mapv以防止堆栈溢出：

#!/bin/bash lein-exec                                                           


(println (reduce (fn [acc _]                                                    
                   ;;(mapv #(inc %) acc))                                       
                   (map #(inc %) acc))                                          
                 (repeat 2 0)                                                   
                 (range (long 1e6))))

~

我不明白 acc 懒惰时是如何处理的。感谢您的见解。

Answer 1

基本上，您得到的是大量嵌套的惰性序列，在戳时会导致堆栈溢出。

让我们看一个更小的例子：

(reduce (fn [acc _]
          (map inc acc))
        (repeat 2 0)
        (range 3))

由于 map 是懒惰的，上面的结果将是下一个：

(map inc (map inc (map inc (0 0)))

所以你不是急于将acc映射到inc，而是只是将惰性序列一个一个地插入另一个，这将在以后实现。

回到原来的例子，其中 range 取 1e6，结果如下：

(map inc 
    (map inc 
         (<... rougly 1e6 nested lazy sequences here ...>
            (map inc (0 0))) ...)

实现这一点会消耗大约1e6个堆栈帧，这肯定会导致堆栈溢出。

在 mapv 的情况下不涉及懒惰并且 acc 立即实现，因此您的示例的结果将是 [1000000 1000000] 在 reduce 完成后立即。

reduce 和 map 累加器产生堆栈溢出

reduce and map on accumulator produces stack overflow

stack-overflow

clojure

lazy-evaluation