clojure中的插入排序拋出StackOverFlow錯誤

(defn insert [s k] 
    (let [spl (split-with #(< % k) s)] 
     (concat (first spl) (list k) (last spl)))) 

(defn insert-sort [s] 
    (reduce (fn [s k] (insert s k)) '() s)) 

(insert-sort (reverse (range 5000)))

拋出一個堆棧溢出錯誤。我在這裏做錯了什麼？clojure中的插入排序拋出StackOverFlow錯誤

來源

2012-03-22 user869081

有趣的是我的repl它早在列表大小891處去掉 – jayunit100 2012-03-25 23:46:13

同樣的問題與Recursive function causing a stack overflow。 Concat建立了一堆嵌套的懶序列，例如（concat（concat（concat ...）））而沒有做任何實際的工作，然後當你強制第一個元素時，所有的concat都必須立刻解決，疊加。

來源

2012-03-22 03:57:00 amalloy

您的reduce每次創建一個新列表。

我的實現：

(defn- insert [el seq] 
    (if (empty? seq) (cons el seq) 
     (if (< el (first seq)) (cons el seq) 
      (cons (first seq) (insert el (rest seq)))))) 

(defn insertion-sort 
    ([seq sorted] 
    (if (empty? seq) sorted 
     (recur (rest seq) (insert (first seq) sorted)))) 
    ([seq] 
    (insertion-sort seq nil)))

來源

2012-03-22 00:42:46 mishadoff

我不太明白。如果我用我的替換插入，我仍然有一個堆棧溢出錯誤。（defn insert [sk] （let [spl（split-with＃（<％k）s）] （concat（first spl）（list k）（last spl））））（defn insertion-sort （[seq sorted] （if（empty？seq）sorted （recur（rest seq）（insert sorted（first seq）））））（[seq] （insert-sort seq nil））） – user869081 2012-03-22 01:06:03

yes，但每次你都會減少。我正在使用尾遞歸調用。請參閱http://clojuredocs.org/clojure_core/clojure.core/recur – mishadoff 2012-03-22 10:26:45

正如主要答案所示，列表concat是罪犯。呼喚「DOALL」，與列表作爲輸入...將導致ISEQ：

;;insertion sort helper 
    (defn insert [s k] 
     ;;find the insert point 
     (let [spl (split-with #(< % k) s) 
       ret (concat (first spl) (list k) (last spl))] 
       (doall ret))) 

    ;;insertion sort 
    (defn insert-sort [s] 
     (reduce (fn [s k] (insert s k)) '() s))

別急......是序列還是懶惰？

上面的代碼有趣的是，下面的代碼表明這個序列確實還是很懶！

;;insertion sort helper 
(defn insert [s k] 
    ;;find the insert point 
    (let [spl (split-with #(< % k) s) 
      ret (concat (first spl) (list k) (last spl)) 
      ret2 (doall ret) 
      _ (println "final " (.getClass ret2))] 
      ret2)) 

;;insertion sort 
(defn insert-sort [s] 
    (reduce (fn [s k] (insert s k)) '() s))

所以，如果名單仍然懶惰，那麼爲什麼不使用的doall的修復什麼？

「doall」函數不適合返回「非懶惰」列表，而是它確保它返回的列表將通過完整遍歷進行評估。

因此，問題的實質是多重函數調用，懶惰無疑與原始問題中代碼的這一方面有關，但它不是溢出的「主要」來源。

來源

2012-03-26 00:32:34 jayunit100

clojure中的插入排序拋出StackOverFlow錯誤

回答

相關問題