Вставка сортировки в clojure выдает ошибку StackOverFlow - PullRequest
Новая
       44

Вставка сортировки в clojure выдает ошибку StackOverFlow

0 голосов
/ 22 марта 2012 
(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)))

выбрасывает стек по ошибке потока.Что я тут не так делаю?

Ответы [ 3 ]

3 голосов
/ 22 марта 2012

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

2 голосов
/ 22 марта 2012

Ваш 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)))
1 голос
/ 26 марта 2012

Как следует из основного ответа, список 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» не гарантируется для возврата«не ленивый» список, но, скорее, он гарантирует, что список, который он возвращает, будет оценен путем полного анализа.

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

...