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.
Note that "compose" is a procedure, so you don't want to be calling it
on each iteration.
You still need a "number->english-letter-count" procedure.
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/"; 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.
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.
--
http://www.neilvandyke.org/
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
