clojure - (另一个)StackOverflow with loop/recur

Question

我知道这是一个反复出现的问题(这里,这里,等等),我知道这个问题与创建延迟序列有关,但我不明白它为什么会失败.

问题:我编写了一个(不是很好的)quicksort算法来排序使用loop/recur的字符串.但是应用于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并且在添加doall之前concat解决了堆栈溢出问题.但为什么？

Answer 1

这是concat的两个版本的代码的一部分.

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

请注意,它使用了另外两个函数lazy-seq,和seq.lazy-seq有点像lambda,它包装一些代码而不执行它.lazy-seq块内的代码必须产生某种序列值.当你调用任何序列操作时lazy-seq,它将首先评估代码("实现"懒惰的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等.所以这是一个实现一切的连锁反应,每个步骤都会消耗一个堆栈帧.

(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)