为什么此代码报告Clojure中的堆栈溢出

Question

这是一个简单的尝试，重现一些Ross Ihaka作为R性能不佳的例子。我很好奇Clojure的持久性数据结构是否能提供任何改进。 （https://www.stat.auckland.ac.nz/~ihaka/downloads/JSM-2010.pdf）

然而，我甚至没有得到一个基础，报告了Stack Overflow，而且没有其他的东西要去。有任何想法吗？如果问题有一个我错过的明显答案，请提前道歉......

; Testing Ross Ihaka's example of poor R performance
; against Clojure, to see if persisntent data structures help

(def dd (repeat 60000 '(0 0 0 0)))

(defn repl-row [d i new-r]
   (concat (take (dec i) d) (list new-r) (drop i d)))

(defn changerows [d new-r]
  (loop [i 10000
         data d]
    (if (zero? i)
      data
      (let [j (rand-int 60000)
            newdata (repl-row data j new-r)]
        (recur (dec i) newdata)))))


user=> (changerows dd '(1 2 3 4))

StackOverflowError   clojure.lang.Numbers.isPos (Numbers.java:96)

此外，如果任何人有任何想法如何在上面的例子中使用持久的功能数据结构以获得最佳利益，我将非常渴望听到。报告的不使用不可变结构的加速（上面的链接）大约是500％！

Answer 1

查看StackOverflowError的堆栈跟踪，这似乎是一个“爆炸性的thunk”（懒惰/暂停计算）问题，与您示例中的递归无明显关联：

java.lang.StackOverflowError
    at clojure.lang.RT.seq(RT.java:528)
    at clojure.core$seq__5124.invokeStatic(core.clj:137)
    at clojure.core$concat$cat__5217$fn__5218.invoke(core.clj:726)
    at clojure.lang.LazySeq.sval(LazySeq.java:40)
    at clojure.lang.LazySeq.seq(LazySeq.java:49)
    at clojure.lang.RT.seq(RT.java:528)
    at clojure.core$seq__5124.invokeStatic(core.clj:137)
    at clojure.core$take$fn__5630.invoke(core.clj:2876)

更改此行以将newdata实现为向量可解决此问题：

(recur (dec i) (vec newdata))

这个解决方法是通过强制concat的懒惰序列在每个步骤中实现来解决在repl-row中使用concat的问题。 concat返回懒惰的序列，并且在你的loop / recur中你传入之前的concat调用的惰性/未评估结果作为后续concat调用的输入，这些调用基于先前的未实现的懒惰序列返回更多的懒惰序列。最终的concat产生的延迟序列直到循环结束才实现，这导致堆栈溢出，因为它依赖于数千个先前的concat产生的惰性序列。

此外，如果任何人有任何想法如何在上面的例子中使用持久的功能数据结构以获得最佳利益，我将非常渴望听到。

因为在这里使用concat似乎只是简单地替换集合中的元素，所以我们可以通过使用向量和qazxs将新项目转换为向量的正确位置来获得相同的效果：

assoc

请注意，没有更多的

(def dd (vec (repeat 60000 '(0 0 0 0))))

(defn changerows [d new-r]
  (loop [i 10000
         data d]
    (if (zero? i)
      data
      (let [j (rand-int 60000)
            newdata (assoc data j new-r)]
        (recur (dec i) newdata)))))

函数，我们只使用索引和新值将repl-row导入assoc。在与data进行了一些基本的基准测试之后，这种方法似乎要快很多倍：

time

这是另一种解决方法，通过将一系列替换视为无限的替换步骤序列，然后从该序列中取样：

"Elapsed time: 75836.412166 msecs" ;; original sample w/fixed overflow
"Elapsed time: 2.984481 msecs"     ;; using vector+assoc instead of concat