Lazy sequence min-max finder stackoverflow problem

Question

 (defn min-max-by-columns [s]
   (reduce (fn [[smallest largest] y]
            [(map min smallest y) (map max largest y)])
      [(first s) (first s)]
      s))

I'm trying to find out the max and min of each column of a large table (sequence of fixed length sequences)

The above code works fine for small tables, but for large tables I get a stackoverflow error

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)

...

Am I holding on to the head because of the line [(first s) (first s)]? I need these values for the algorithm to work.

How can I fix this?

It doesn't look to me like you're holding on to the head, but I'd be curious to see what happened if you just did a min or max and therefore could take the [(first s) (first s)] out of the equation, e.g., (defn min-columns [s] (reduce (fn [x y] (map min x y)) s)). — dfan
– dfan, Commented Apr 26, 2011 at 18:51

bmillare · Accepted Answer · 2011-04-27 13:33:45Z

3

I seemed to find the solution. As amalloy explained, the (map smallest x) and (map max largest x) is being realized all at once. I am, however, trying to solve a different problem than what he is solving. Luckily, his insight helped lead me to the solution; the trick is to wrap a doall around each map so that they are realized during intermediate steps as opposed to all at the once in the end.

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

edited Apr 27, 2011 at 13:33

answered Apr 26, 2011 at 19:15

bmillare

4,2332 gold badges27 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

amalloy · Accepted Answer · 2011-04-26 18:50:49Z

2

(map min smallest y) doesn't make any sense. Instead of computing a new smallest number, you're returning a lazy sequence of [(min smallest) (min y)]. Eventually a zillion of these lazy maps pile up on top of each other, and you realize them all at once. This is easy to fix since you don't want to map anything to begin with!

I'm a bit surprised you say this is "working" for small sequences. I can see it not blowing up the stack (of course), but I don't see how it could ever compute the right answer. Anyway, my solution would be

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

answered Apr 26, 2011 at 18:50

amalloy

93k8 gold badges149 silver badges216 bronze badges

1 Comment

dfan Over a year ago

I think the two of you are solving different problems. He's taking a 2-D table and is computing two lists, one with the smallest number in each column and one with the largest number in each column. (min-max-by-columns [[1 2 9] [4 5 6] [7 8 3]]) -> [(1 2 3) (7 8 9)]. Maybe he just needs to be strict in his intermediate steps?

Collectives™ on Stack Overflow

Lazy sequence min-max finder stackoverflow problem

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related