[racket] A question about code-style (and memory usage)

Neil,

Thanks for taking the time to comment.


On Sun, Jul 24, 2011 at 09:34, Neil Van Dyke <neil at neilvandyke.org> wrote:

> Rodolfo Carvalho wrote at 07/24/2011 12:25 AM:
>
>  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.
>>
>
> 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.
>


Ok. I'll keep that one for the "one-liner contest" :D

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.



>
> Note that "compose" is a procedure, so you don't want to be calling it on
> each iteration.
>


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.
In solution 1 "compose" is evaluated only once, I believe.



>
> You still need a "number->english-letter-count" procedure.
>


Yes. Yesterday I didn't mean to "solve" the problem, nor to solve it
efficiently. It was more of an exploration.



>
> Were I implementing this Project Euler solution for a reusable library, I
> would probably: (1) adapt "number->english" from "
> http://www.neilvandyke.org/**numspell-scheme/<http://www.neilvandyke.org/numspell-scheme/>"
> 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-**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.
>


Yes, were I implementing this problem efficiently I would not generate the
intermediate string representation of numbers -- it is useless in this case.
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.
(The plots that I've generated so far induce me into confirming that
conclusion.)



>
> 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.
>
> 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.
>


Thanks for pointing me to named-let.

Previously I have also implemented 2 others solutions using recursion, and
earlier today after reading this email I wrote another one using named-let.


; Solve recursively // Solution 3
(define (recur-letter-count-of-integers-up-to n)
  (if (zero? n)
      0
      (+ ((compose string-length integer->string) n)
         (recur-letter-count-of-integers-up-to (sub1 n)))))

; Solve recursively, tail call // Solution 4
(define (tail-letter-count-of-integers-up-to n [acc 0])
  (if (zero? n)
      acc
      (tail-letter-count-of-integers-up-to
       (sub1 n)
       (+ (string-length (integer->string n))
          acc))))

; Solve using a named-let // Solution 5
(define (let-letter-count-of-integers-up-to n)
  (let f ([i n]
          [acc 0])
    (if (zero? i)
        acc
        (f (sub1 i) (+ (string-length (integer->string i))
                       acc)))))



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).
I couldn't think of a reason to explain that.

The first one using recursion in a bad way (3) was the worst in execution
time.

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.

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:
http://bazaar.launchpad.net/~rhcarvalho/+junk/racket/view/head:/project-euler-17.rkt

[]'s

Rodolfo Carvalho
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20110725/ef108e38/attachment.html>