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
