Reposting this from earlier mail about Euler 14.
(defn cseq [n]
(if (= 1 n)
[1]
(cons n (cseq (if (even? n)
(/ n 2)
(+ (* 3 n) 1 ))))))
(apply max-key count (map cseq (range 1 1000000)))
Gives a heap error.
cseq is at most 525 elements long.
2011/1/17 Mark Engelberg <mark.engelb...@gmail.com>
> On Mon, Jan 17, 2011 at 11:55 AM, Andreas Liljeqvist <bon...@gmail.com>
> wrote:
> > I don't see why the cseq's have to be lazy, they are at the most 525
> > elements long.
> > shouldn't each sequence only be produced when it is reduced in max-key
> and
> > then discarded?
>
> You're right, the chains aren't as long as I thought. I can't think
> of any good explanation as to why max-key blows the heap when cseq is
> non-lazy and doesn't when cseq is lazy. (I confirmed that on my
> system, I get the same behavior as you, even set to a 1600MB heap
> size).
>
> Interestingly, this:
> (apply max (map count (map cseq (range 1 1000000))))
> works just fine with non-lazy seq.
>
> The only real difference between this and the max-key version is that
> reducing the max-key requires keeping around the longest list so far,
> whereas this one just keeps around the count. But keeping around a
> 525 element list shouldn't be enough to overflow the heap.
>
> I've tried to figure out:
> Could max-key be holding on to the heads of these lists?
> Could this be an effect of chunked sequences?
>
> The chunked sequences explanation seems almost plausible. You could
> in theory have 32 lists realized at once, plus the biggest one you've
> seen so far. But even in the worst-case scenario, you're talking
> about 15000 elements, and I don't see how that could overflow the
> heap. Just out of curiosity, I tried this with an unchunked range,
> and still got the heap overflow, so I don't see how it could be a
> chunking issue.
>
> Furthermore if either of these were the problem, you'd expect to see
> the same problem with lazy cseq, because ultimately count has to
> realize the lazy cseq, so if too many heads were being retained at
> once, the lazy version would exhibit the same heap space problem.
>
> This leads to the more disturbing possibility that maybe there's a
> garbage collection flaw relating to non-lazy lists.
>
> I'd love to see some more people investigate this and see if we can
> come up with a good explanation as to why the original poster's code
> overflows the heap space.
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clojure@googlegroups.com
> Note that posts from new members are moderated - please be patient with
> your first post.
> To unsubscribe from this group, send email to
> clojure+unsubscr...@googlegroups.com<clojure%2bunsubscr...@googlegroups.com>
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
