Lazy sequence min-max finder проблема переполнения стека - PullRequest
Новая
       32

Lazy sequence min-max finder проблема переполнения стека

4 голосов
/ 26 апреля 2011 
 (defn min-max-by-columns [s]
   (reduce (fn [[smallest largest] y]
            [(map min smallest y) (map max largest y)])
      [(first s) (first s)]
      s))

Я пытаюсь узнать максимальное и минимальное значение каждого столбца большой таблицы (последовательность последовательностей фиксированной длины)

Приведенный выше код отлично работает для небольших таблиц, но для больших таблиц я получаю ошибку stackoverflow 

clojure.core/map/fn--3594 (core.clj:2370)
clojure.lang.LazySeq.sval (LazySeq.java:42)
clojure.lang.LazySeq.seq (LazySeq.java:60)
clojure.lang.RT.seq (RT.java:447)
clojure.core/seq (core.clj:133)
clojure.core/map/fn--3594 (core.clj:2371)
clojure.lang.LazySeq.sval (LazySeq.java:42)
clojure.lang.LazySeq.seq (LazySeq.java:60)
clojure.lang.RT.seq (RT.java:447)
clojure.core/seq (core.clj:133)
clojure.core/map/fn--3594 (core.clj:2371)
clojure.lang.LazySeq.sval (LazySeq.java:42)
clojure.lang.LazySeq.seq (LazySeq.java:60)
clojure.lang.RT.seq (RT.java:447)
clojure.core/seq (core.clj:133)
clojure.core/map/fn--3594 (core.clj:2371)

...

Я держусь за голову из-за линии [(первые) (первые)]? Мне нужны эти значения для работы алгоритма.

Как я могу это исправить?

Ответы [ 2 ]

3 голосов
/ 26 апреля 2011

Кажется, я нашел решение.Как объяснил Амаллой, (карта наименьшего x) и (карта наименьшего наибольшего x) реализуются одновременно.Я, однако, пытаюсь решить проблему, отличную от той, которую он решает.К счастью, его понимание помогло привести меня к решению;Хитрость заключается в том, чтобы обернуть замки вокруг каждой карты, чтобы они реализовывались на промежуточных этапах, а не на всех сразу в конце. 

 (defn min-max-by-columns [s]
   (reduce (fn [[smallest largest] y]
         [(doall (map min smallest y)) (doall (map max largest y))])
       [(first s) (first s)]
       s))
2 голосов
/ 26 апреля 2011

(map min smallest y) не имеет никакого смысла.Вместо того, чтобы вычислять новое наименьшее число, вы возвращаете ленивую последовательность [(min smallest) (min y)].В конце концов, миллионы этих ленивых карт накапливаются друг на друге, и вы понимаете их все сразу.Это легко исправить, поскольку вы не хотите ничего начинать с карты!

Я немного удивлен, что вы говорите, что это "работает" для небольших последовательностей.Я могу видеть, что это не взрывает стек (конечно), но я не вижу, как это могло когда-либо вычислить правильный ответ.Во всяком случае, мое решение будет 

(defn min-max-by-columns [[x & xs]]
  (reduce (fn [[smallest largest] x]
            [(min smallest x) (max largest x)])
          [x x]
          xs))
...