<div dir="ltr">Thanks Daniel! <br><br>I only asked, because I was comparing the versions:<br><br>1) Steve&#39;s first version, without g x took forever to run and ate all the stack.<br>2) Mine (with Map) ran somewhat fast, but it takes almost 2 minutes running and eats 48MB of stack<br>
3) Steve&#39;s last version (with g x) took less than 30s on my machine and needed no more than 8MB of stack.<br><br><br>If I understood it right, using (g x) on foldl&#39; forced the strictness of the thunk (acc+1), without the need of using the bang pattern.<br>
<br>I&#39;ll try to play with the strictness on my code, trying to take advantage of both the Map and strictness.<br><br>Rafael<br><br><br><div class="gmail_quote">On Mon, Jul 28, 2008 at 23:15, Daniel Fischer <span dir="ltr">&lt;<a href="mailto:daniel.is.fischer@web.de">daniel.is.fischer@web.de</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Am Dienstag, 29. Juli 2008 01:53 schrieb Rafael Gustavo da Cunha Pereira<br>
Pinto:<br>
<div class="Ih2E3d">&gt; Since this is the &quot;beginners&quot; list, could someone explain me why using g<br>
&gt; made everything run like the wind, with almost no memory?<br>
<br>
</div>I&#39;d rate &quot;run like the wind&quot; as an exaggeration since the completely<br>
unoptimised C version runs in 1.6 seconds vs. 54 seconds for the code below<br>
(49 seconds if using Int for the chain length) on my box. And the &quot;g&quot; isn&#39;t<br>
important for speed or memory, just for getting the correct result.<br>
<br>
Two factors make it run in constant memory without stack overflow:<br>
1. strictness<br>
2. laziness.<br>
<br>
The strictness of foldl&#39; is the reason that every g k is evaluated without<br>
delay and can immediately be thrown away (unless it&#39;s the maximum so far, in<br>
which case the previous maximum can be discarded) and the laziness of map and<br>
enumFromTo (remember that [a .. b] is syntactic sugar for enumFromTo a b)<br>
allows the list to be consumed as it is generated.<br>
<br>
Let us trace a few evaluation steps of answer:<br>
answer<br>
---&gt; foldl&#39; max (0,0) $ map g (enumFromTo 1 999999)<br>
-- First, we must see whether the list is empty or not,<br>
-- 1 &lt;= 999999, so the list is not empty<br>
---&gt; foldl&#39; max (0,0) $ map g (1 : enumFromTo (1+1) 999999)<br>
---&gt; foldl&#39; max (0,0) $ g 1 : map g (enumFromTo (1+1) 999999)<br>
---&gt; foldl&#39; max (max (0,0) (g 1)) $ map g (enumFromTo (1+1) 999999)<br>
-- Now, due to the strictness of foldl&#39;, max (0,0) (g 1) has to be evaluated<br>
-- far enough to know if it is _|_ or not. For that, we obviously have to<br>
-- compare (0,0) and g 1, hence we must evaluate g 1 far enough to see if<br>
-- (0,0) &lt;= g 1. Now g 1 = (f 1 1, 1) and we must check whether 0 &lt;= f 1 1.<br>
-- However, f 1 1 = 1, so yes, and max (0,0) (g 1) turns out to be (1,1)<br>
---&gt; foldl&#39; max (1,1) $ map g (enumFromTo (1+1) 999999)<br>
-- Now to decide if the list is empty, (1+1) must be compared to 999999,<br>
-- for that it must be evaluated, so<br>
---&gt; foldl&#39; max (1,1) $ map g (2 : enumFromTo (2+1) 999999)<br>
---&gt; foldl&#39; max (1,1) $ g 2 : map g (enumFromTo (2+1) 999999)<br>
---&gt; foldl&#39; max (max (1,1) (g 2)) $ map g (enumFromTo (2+1) 999999)<br>
-- Is max (1,1) (g 2) _|_ or not? To find out evaluate g 2 = (2,2)<br>
---&gt; foldl&#39; max (2,2) $ map g (enumFromTo (2+1) 999999)<br>
---&gt; foldl&#39; max (2,2) $ map g (3 : enumFromTo (3+1) 999999)<br>
---&gt; foldl&#39; max (2,2) $ g 3 : map g (enumFromTo (3+1) 999999)<br>
---&gt; foldl&#39; max (max (2,2) (g 3)) $ map g (enumFromTo (3+1) 999999)<br>
---&gt; foldl&#39; max (8,3) $ map g (enumFromTo (3+1) 999999)<br>
...<br>
---&gt; foldl&#39; max (max (8,3) (g 4)) $ map g (enumFromTo (4+1) 999999)<br>
---&gt; foldl&#39; max (8,3) $ map g (enumFromTo (4+1) 999999)<br>
<br>
and so on. Hardly any memory needed.<br>
But you have more than 100,000,000 calls to f.<br>
Now if you store previous results in a Map, you save many of these calls (to<br>
rank in your code), but you pay for it with memory usage (and a couple of<br>
million expensive insertions into the Map). For every entry in the Map, apart<br>
from the space for key and value, you also have an Int holding the size of<br>
the subtree and pointers to the two subtrees of the node, on a 32-bit box<br>
that&#39;s a theoretical minimal overhead of 12 bytes per entry, probably rather<br>
20 in reality, so a Map Integer Integer with one million entries would use<br>
some 30 MB memory.<br>
<br>
Hope that helps,<br>
<font color="#888888">Daniel<br>
</font><div><div></div><div class="Wj3C7c"><br>
&gt;<br>
&gt; I am puzzled! :-(<br>
&gt;<br>
&gt; On Mon, Jul 28, 2008 at 17:32, Steve Klabnik &lt;<a href="mailto:steve.klabnik@gmail.com">steve.klabnik@gmail.com</a>&gt;wrote:<br>
&gt; &gt; Finally, what I ended up doing:<br>
&gt; &gt;<br>
&gt; &gt; f :: Integer -&gt; Integer -&gt; Integer<br>
&gt; &gt; f acc x<br>
&gt; &gt;<br>
&gt; &gt; &nbsp; &nbsp; | x == 1 = acc<br>
&gt; &gt; &nbsp; &nbsp; |<br>
&gt; &gt; &nbsp; &nbsp; &nbsp; &nbsp; | even x = f (acc + 1) (x `div` 2)<br>
&gt; &gt; &nbsp; &nbsp; &nbsp; &nbsp; | otherwise = f (acc + 1) (3 * x + 1)<br>
&gt; &gt;<br>
&gt; &gt; g :: Integer -&gt; (Integer, Integer)<br>
&gt; &gt; g x = (f 1 x, x)<br>
&gt; &gt;<br>
&gt; &gt; answer = (foldl&#39; max (0,0)) $ map g [1 .. 999999]<br>
&gt; &gt;<br>
&gt; &gt;<br>
&gt; &gt; main = putStrLn( show answer)<br>
<br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Rafael Gustavo da Cunha Pereira Pinto<br>Electronic Engineer, MSc.<br>
</div>