[racket] Why is this slow?
The `range` function produces a list, which is a big overhead for each time
the inner loop executes. There's a big improvement changing the inner loop
sequence clause to just [p n]. There's a bit more improvement making that
[p (in-range n)], which is recognized statically at expansion time by the
`for` loop to produce better code. See:
http://docs.racket-lang.org/guide/for.html#(part._for-performance)
Filtering the final list during building is also an improvement:
(for/list ([i (range 2 n)]
#:when (vector-ref A i))
i)
And let's make it more consistent with the comment style, and consistent
with the above changes. This appears to speed it up even more, although
I didn't investigate where exactly the big win(s) were:
#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)))