[racket] Why is this slow?
From: Shannon Severance (srs at s53.me)
Date: Wed Apr 24 05:45:47 EDT 2013 |
|
This one I will need to study, since it uses new to me Racket stuff. And
it is quick. On my machine:
> (time (apply + (gb-sieve-of-eratosthenes n)))
cpu time: 485 real time: 497 gc time: 118
142913828922
Compare:
> (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 in separate email to the list.
On 4/24/13 2:17 AM, "Gary Baumgartner" <gfb at cs.toronto.edu> wrote:
>#lang racket
>
>;; Input: an integer n > 1
>(define (sieve-of-eratosthenes n)
> ;; Let A be an array of Boolean values, indexed by integers 2 to n,
> ;; initially all set to true.
>
> ;; for i = 2, 3, 4, ..., √n :
> ;; when A[i] is true:
> ;; for j = i², i²+i, i²+2i, ..., n:
> ;; A[j] := false
> (define A (make-vector n #t))
> (for ([i (in-range 2 (sqrt n))]
> #:when (vector-ref A i))
> (for ([j (in-range (sqr i) n i)])
> (vector-set! A j #f)))
>
> ;; Now all i such that A[i] is true are prime.
> (for/list ([i (in-range 2 n)]
> #:when (vector-ref A i))
> i))
>
>(time (apply + (sieve-of-eratosthenes 2000000)))