For the sieve, if performance matters, clojure's native data structures may
not be the best choice.
A mutable array of boolean primitives could be more apropos.
(defn prime-sieve [^long n]
(let [^booleans sieve (make-array Boolean/TYPE (inc n))]
...)
... using aset/aget to write/read sieve.
On Tuesday, August 9, 2011 1:18:46 PM UTC-7, Chouser wrote:
>
> On Tue, Aug 9, 2011 at 12:50 PM, Kevin Sookocheff
> <kevin.so...@gmail.com> wrote:
> > Hi,
> >
> > I have a question regarding the map data structure. I'm trying to program
> a
> > Sieve of Eratosthenes using the algorithm at Wikipedia:
> >
> > Input: an integer n > 1
> >
> > Let A be an array of bool values, indexed by integers 2 to n,
> > initially all set to true.
> >
> > for i = 2, 3, 4, ..., while i^2 ≤ n:
> > if A[i] is true:
> > for j = i^2, i^2 + i, i^2 + 2i, ..., while j ≤ n:
> > A[j] = false
> >
> > Now all i such that A[i] is true are prime.
> >
> > I'm having a problem creating the data structure A.
> >
> > What I want to do is create a map of integers from 2 to n all initialized
> to
> > true that I can then prune using the algorithm.
> >
> > Any ideas?
>
> Since the keys are consecutive integers, you might consider a vector
> of booleans:
>
> (def A (vec (repeat (inc n) true)))
>
> You can then use assoc to set any particular index to false:
>
> (assoc A 5 false)
>
> Differences using a vector instead of a hash-map: will stay in numeric
> order, doesn't allow arbitrary dissoc, nth and assoc may be faster,
> use less memory, (vector-of :bool) will definitely use less memory,
> and probably others. Depending on your goals, a vector may or may not
> be preferable to a hash-map.
>
> --Chouser
>
>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
