Сортировка вставками в 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 stack-overflow insertion-sort
person user869081    schedule 22.03.2012    source источник
comment
интересно, в моем ответе он умирает уже при размере списка 891   -  person jayunit100    schedule 26.03.2012

Ответы (3)


arrow_upward
3
arrow_downward

Та же проблема, что и с рекурсивной функцией, вызывающей переполнение стека. Concat создает кучу вложенных ленивых последовательностей, таких как (concat (concat (concat ...))) без выполнения какой-либо реальной работы, а затем, когда вы форсируете первый элемент, все concat должны быть разрешены в один раз, взорвав стек.

person amalloy    schedule 22.03.2012

arrow_upward
2
arrow_downward

Ваш 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)))
person mishadoff    schedule 22.03.2012
comment
Я не совсем понимаю. Если я заменю вашу вставку своей, я все равно получу ошибку переполнения стека. (defn insert [s k] (let [spl (split-with #(‹ % k) s)] (concat (first spl) (list k) (last spl)))) (defn insertion-sort ([seq sorted] (if (пусто? seq) отсортировано (recur (остаток seq) (вставить отсортировано (first seq) )))) ([seq] (insertion-sort seq nil))) - person user869081; 22.03.2012
comment
да, но вы все равно каждый раз нажимаете уменьшить. Я использую вызовы хвостовой рекурсии. см. recur clojuredocs.org/clojure_core/clojure.core/recur - person mishadoff; 22.03.2012

arrow_upward
1
arrow_downward

Как следует из основного ответа, список 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" не гарантирует возврат "неленивого" списка, но, скорее, она гарантирует, что список, который она ДЕЙСТВИТЕЛЬНО возвращает, будет оценен путем полного обхода.

Таким образом, суть проблемы заключается в множественных вызовах функций, лень, безусловно, связана с этим аспектом кода в вашем исходном вопросе, но это не «первичный» источник переполнения.

person jayunit100    schedule 26.03.2012