<div dir="ltr">Hi: beware that timing inside DrRacket can be very misleading (DrRacket is doing lots of stuff). See:<div><br></div><div> <a href="http://docs.racket-lang.org/guide/performance.html?q=performance">http://docs.racket-lang.org/guide/performance.html?q=performance</a></div>
<div><br></div><div style>for more details.</div><div style><br></div><div style>Robby</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Apr 24, 2013 at 4:38 AM, Shannon Severance <span dir="ltr"><<a href="mailto:srs@s53.me" target="_blank">srs@s53.me</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Jordan,<br>
<br>
I'm new to Racket, so I do not fully understand your implementation of<br>
the sieve-of-eratosthenes. So I can't comment one why it is slow. But<br>
I have a faster version, and maybe some differences will stand out to<br>
investigate.<br>
<br>
I did notice that your when your implementation of the sieve was<br>
running, the little GC icon was always atleast flashing and sometimes<br>
solid. Lots of intermediate results being created that need GCed? If<br>
you compare my faster implementation of the sieve below, it has far<br>
fewer arithmetic operations and fewer intermediate results.<br>
<br>
My version is pretty close to what I would have done in r5rs<br>
scheme. But I don't have the scheme library functions memorized and<br>
used the Racket documentation to find appropriate Racket functions,<br>
which may or may not have been in r5rs.<br>
<br>
#lang racket<br>
<br>
(define (soe n)<br>
(define sqrt-n (inexact->exact (ceiling(sqrt n))))<br>
<br>
(define primes (build-vector (add1 n) (λ (_) _)))<br>
(vector-copy! primes 0 (vector #f #f))<br>
<br>
(define (cross-off-multiples prime)<br>
(define (cross-off-multiples-iter not-prime)<br>
(if (<= not-prime n)<br>
[begin<br>
(vector-set! primes not-prime #f)<br>
(cross-off-multiples-iter (+ not-prime prime))]<br>
(visit-candidates (add1 prime))))<br>
(cross-off-multiples-iter (expt prime 2)))<br>
<br>
(define (visit-candidates prime-candidate)<br>
(cond [(> prime-candidate sqrt-n) primes]<br>
[(not (vector-ref primes prime-candidate)) (visit-candidates<br>
(add1 prime-candidate))]<br>
[(vector-ref primes prime-candidate) (cross-off-multiples<br>
prime-candidate)]))<br>
(filter (λ (_) _) (vector->list (visit-candidates 2))))<br>
<br>
I placed the two versions you gave and my version in the same<br>
definitions file. Within the Dr Racket IDE, ran the definitions and<br>
then:<br>
<br>
> (define n (inexact->exact 2e6))<br>
> (time (apply + (filter prime? (range 2 n))))<br>
cpu time: 9788 real time: 9974 gc time: 1851<br>
142913828922<br>
> (time (apply + (soe n)))<br>
cpu time: 1049 real time: 1065 gc time: 311<br>
142913828922<br>
> (time (apply + (sieve-of-eratosthenes n)))<br>
cpu time: 266955 real time: 274532 gc time: 218362<br>
142913828922<br>
<br>
Machine Info:<br>
Model Name: Mac Pro<br>
Model Identifier: MacPro4,1<br>
Processor Name: Quad-Core Intel Xeon<br>
Processor Speed: 2.66 GHz<br>
Number of Processors: 1<br>
Total Number of Cores: 4<br>
L2 Cache (per Core): 256 KB<br>
L3 Cache: 8 MB<br>
Memory: 6 GB<br>
<br>
System Version: OS X 10.8.3 (12D78)<br>
Kernel Version: Darwin 12.3.0<br>
Boot Volume: Macintosh SSD<br>
Boot Mode: Normal<br>
Secure Virtual Memory: Enabled<br>
<br>
DrRacket version 5.3.3<br>
Memory Limit 4096MB<br>
<br>
Hoping there is a clue above.<br>
<span class="HOEnZb"><font color="#888888"><br>
-- Shannon<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
<br>
____________________<br>
Racket Users list:<br>
<a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br>
</div></div></blockquote></div><br></div>