<div class="gmail_quote">Neil,</div><div class="gmail_quote"><br></div><div class="gmail_quote">Thanks for taking the time to comment.</div><div class="gmail_quote"><br></div><div class="gmail_quote"><br></div><div class="gmail_quote">
On Sun, Jul 24, 2011 at 09:34, Neil Van Dyke <span dir="ltr"><<a href="mailto:neil@neilvandyke.org" target="_blank">neil@neilvandyke.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Rodolfo Carvalho wrote at 07/24/2011 12:25 AM:<div><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
For me solution 1 is compact, however it allocates the list without need (which gives out of memory error for large N). Solution 2 is more memory efficient, but more verbose.<br>
</blockquote>
<br></div>
I think that solution 2 is on the path to being relatively better, due to space efficiency, as you said. Solution 1 is the kind of thing you might do if you're teaching concepts like "apply" or if you're more experienced with conventional mathematics than programming, but that you probably wouldn't do in a reusable library.<br>
</blockquote><div><br></div><div><br></div><div>Ok. I'll keep that one for the "one-liner contest" :D</div><div><br></div><div>But to my surprise it performed faster than sol. 2 on my tests for "small enough N". Clearly for large N it goes out of memory and/or takes a lot of time paginating.</div>
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Note that "compose" is a procedure, so you don't want to be calling it on each iteration.<br></blockquote><div><br></div><div><br></div><div>That's right. As one might guess I've taken it from solution 1 down to solution 2 but it should be written differently to avoid the excessive (and useless) calls.</div>
<div>In solution 1 "compose" is evaluated only once, I believe.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
You still need a "number->english-letter-count" procedure.<br></blockquote><div><br></div><div><br></div><div>Yes. Yesterday I didn't mean to "solve" the problem, nor to solve it efficiently. It was more of an exploration.</div>
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Were I implementing this Project Euler solution for a reusable library, I would probably: (1) adapt "number->english" from "<a href="http://www.neilvandyke.org/numspell-scheme/" target="_blank">http://www.neilvandyke.org/<u></u>numspell-scheme/</a>" to use "and" and no punctuation; (2) use "string-length" and that new "number->problem-english" procedure to have a slow initial implementation for the problem solution; (3) adapt "number->problem-english" to be "number->problem-english-<u></u>letter-count" without doing the string ports or other string allocation; (4) test the two implementations against each other; (5) investigate a potential third solution, looking at the algorithm and number patterns, to see whether I can make the the entire program or just the letter-counting procedure be constant-time.<br>
</blockquote><div><br></div><div><br></div><div>Yes, were I implementing this problem efficiently I would not generate the intermediate string representation of numbers -- it is useless in this case.</div><div>There is a linear relationship between N and the number of letters used up to N, which makes me believe that (5) is the way to go.</div>
<div>(The plots that I've generated so far induce me into confirming that conclusion.)</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Were I doing this solution for homework or to post on the Project Euler site, in step #1 above, I would write a new "number->problem-english" procedure from scratch, rather than adapt the one from the PLaneT package.<br>
<br>
After all the inner-loop code has been optimized, if you wanted to shave a couple more instructions off the iteration over 1..1000, you could try named-"let" and counting down (so that your test for loop exit is "zero?"), and see whether that's any faster. That's how I'd write it normally, as a matter of personal style, but I'm not certain that'd be faster in current version of Racket. For a reusable library, you probably wouldn't care about any difference, but you might care if you're trying to win questionable Internet contests about whose language could beat up who else's language.<br>
</blockquote><div><br></div><div><br></div><div>Thanks for pointing me to named-let.</div><div><br></div><div>Previously I have also implemented 2 others solutions using recursion, and earlier today after reading this email I wrote another one using named-let.</div>
<div><br></div><div><br></div><div><div>; Solve recursively // Solution 3</div><div>(define (recur-letter-count-of-integers-up-to n)</div><div> (if (zero? n)</div><div> 0</div><div> (+ ((compose string-length integer->string) n)</div>
<div> (recur-letter-count-of-integers-up-to (sub1 n)))))</div><div><br></div><div>; Solve recursively, tail call // Solution 4</div><meta http-equiv="content-type" content="text/html; charset=utf-8"><div>(define (tail-letter-count-of-integers-up-to n [acc 0])</div>
<div> (if (zero? n)</div><div> acc</div><div> (tail-letter-count-of-integers-up-to</div><div> (sub1 n)</div><div> (+ (string-length (integer->string n))</div><div> acc))))</div><div><br>
</div><div>; Solve using a named-let // Solution 5</div><meta http-equiv="content-type" content="text/html; charset=utf-8"><div>(define (let-letter-count-of-integers-up-to n)</div><div> (let f ([i n]</div><div> [acc 0])</div>
<div> (if (zero? i)</div><div> acc</div><div> (f (sub1 i) (+ (string-length (integer->string i))</div><div> acc)))))</div></div><div><br></div><div><br></div><div><br></div><div>
In my experiments, when I analyzed values up to 100000 (one hundred thousand), the solution using named-let (5) was consistently faster than the recursive/tail call (4).</div>
<div>I couldn't think of a reason to explain that.</div><div><br></div><div>The first one using recursion in a bad way (3) was the worst in execution time.</div><div><br></div><div>However, analyzing a range up to 1000000 (one million) changes the "big picture", so that comparing the speed of the implementations is not independent of input range.</div>
<div><br></div><div>Here's the code I am using to run the different implementations, time the execution, generate tables and plots and put it all into slides:</div><div><meta http-equiv="content-type" content="text/html; charset=utf-8"><a href="http://bazaar.launchpad.net/~rhcarvalho/+junk/racket/view/head:/project-euler-17.rkt">http://bazaar.launchpad.net/~rhcarvalho/+junk/racket/view/head:/project-euler-17.rkt</a></div>
<div><br></div><div>[]'s</div><div><br></div><div>Rodolfo Carvalho</div><meta http-equiv="content-type" content="text/html; charset=utf-8"></div>