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