recursion - clojure - (另一个)带有循环/递归的 StackOverflow

Question

我知道这是一个重复出现的问题( here 、 here 等)，并且我知道该问题与创建惰性序列有关，但我不明白为什么它失败了。

问题:我编写了一个(不是很好)快速排序算法来对使用循环/递归的字符串进行排序。但应用于 10000 个元素时，我得到一个 StackOverflowError:

(defn qsort [list]
  (loop [[current & todo :as all] [list] sorted []]
    (cond 
       (nil? current) sorted 
       (or (nil? (seq current)) (= (count current) 1)) (recur todo (concat sorted current))
       :else (let [[pivot & rest] current
                  pred #(> (compare pivot %) 0)
                  lt (filter pred rest)
                  gte (remove pred rest)
                  work (list* lt [pivot] gte todo)] 
                (recur work sorted)))))

我是这样使用的:

(defn tlfnum [] (str/join (repeatedly 10 #(rand-int 10))))
(defn tlfbook [n] (repeatedly n #(tlfnum)))
(time (count (qsort (tlfbook 10000))))

这是堆栈跟踪的一部分:

  [clojure.lang.LazySeq seq "LazySeq.java" 49]
  [clojure.lang.RT seq "RT.java" 521]
  [clojure.core$seq__4357 invokeStatic "core.clj" 137]
  [clojure.core$concat$fn__4446 invoke "core.clj" 706]
  [clojure.lang.LazySeq sval "LazySeq.java" 40]
  [clojure.lang.LazySeq seq "LazySeq.java" 49]
  [clojure.lang.RT seq "RT.java" 521]
  [clojure.core$seq__4357 invokeStatic "core.clj" 137]]}

据我所知，loop/recur执行尾调用优化，因此没有使用堆栈(实际上是使用递归语法编写的迭代过程)。

阅读其他答案，并且由于堆栈跟踪，我发现 concat 存在问题，并在 concat 解决之前添加 doall堆栈溢出问题。但是...为什么？

Answer 1

这是 concat 的二元版本的部分代码。

(defn concat [x y]
  (lazy-seq
   (let [s (seq x)]
     ,,,))
  )

请注意，它使用了另外两个函数:lazy-seq 和 seq。 lazy-seq 有点像 lambda，它包装了一些代码但尚未执行。 lazy-seq block 内的代码必须产生某种序列值。当您在lazy-seq上调用任何序列操作时，它将首先评估代码(“实现”lazy seq)，然后对结果执行操作。

(def lz (lazy-seq
         (println "Realizing!")
         '(1 2 3)))

(first lz)
;; prints "realizing"
;; => 1

现在试试这个:

(defn lazy-conj [xs x]
  (lazy-seq
   (println "Realizing" x)
   (conj (seq xs) x)))

请注意，它与 concat 类似，它在第一个参数上调用 seq，并返回一个 lazy-seq

(def up-to-hundred
  (reduce lazy-conj () (range 100)))

(first up-to-hundred)
;; prints "Realizing 99"
;; prints "Realizing 98"
;; prints "Realizing 97"
;; ...
;; => 99

即使您只要求第一个元素，它仍然最终实现了整个序列。这是因为实现外层“层”会导致在下一个“层”上调用 seq，从而实现另一个lazy-seq，后者再次调用 seq，依此类推。所以这是一个实现一切的链式 react ，并且每个步骤消耗一个堆栈帧。

(def up-to-ten-thousand
  (reduce lazy-conj () (range 10000)))

(first up-to-ten-thousand)
;;=> java.lang.StackOverflowError

在堆叠 concat 调用时也会遇到同样的问题。这就是为什么 (reduce concat ,,,) 总是有味道，而您可以使用 (apply concat ,,,) 或 (into () cat ,,,).

其他惰性运算符(例如 filter 和 map)也可能出现完全相同的问题。如果您确实在序列上有很多转换步骤，请考虑使用转换器。

;; without transducers: many intermediate lazy seqs and deep call stacks
(->> my-seq
     (map foo)
     (filter bar)
     (map baz)
     ,,,)


;; with transducers: seq processed in a single pass
(sequence (comp
           (map foo)
           (filter bar)
           (map baz))
          my-seq)