# [racket] Why is this slow?

 From: Gary Baumgartner (gfb at cs.toronto.edu) Date: Wed Apr 24 05:17:28 EDT 2013 Previous message: [racket] Why is this slow? Next message: [racket] Why is this slow? Messages sorted by: [date] [thread] [subject] [author]

```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)))

```

 Posted on the users mailing list. Previous message: [racket] Why is this slow? Next message: [racket] Why is this slow? Messages sorted by: [date] [thread] [subject] [author]