減少和地圖上的累加器產生堆棧溢出

Question

爲什麼我需要在這一段代碼與mapv更換map防止堆棧溢出：

#!/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))) 

所以你並不急於與inc映射acc，但只將懶惰的序列放入另一個，這將在事後實現。

再回到其中range1e6取原始示例中，結果將是以下內容：

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

的這個實現將消耗大約1e6堆棧幀，這肯定會導致堆棧溢出。

在mapv的情況下，不涉及懶惰，acc立即實現，因此您的示例的結果將在reduce完成後立即爲[1000000 1000000]。