Creating a map algorithmically

[Kevin Sookocheff]

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?

Thank you,

Kevin

[joegallo]

(zipmap (range 2 (inc n)) (repeat true))

[Bob Shock]

user=> (def n 5)
#'user/n
user=> (zipmap (range 2 (inc n)) (repeat true))
{5 true, 4 true, 3 true, 2 true}
user=>

As a start...

On Aug 9, 10:50 am, Kevin Sookocheff <kevin.sookoch...@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 + 2*i*, ..., *while* *j* ≤ *n*:
>       *A*[*j*] = *false*
>
> Now all *i* such that *A*[*i*] is *true* are prime.

[Chouser]

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

[pmbauer]

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.

[Sunil S Nandihalli]

you should considering looking at clojure.contrib.lazy-seqs/primes to get an idea it is implemented there..
Sunil.

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@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+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[Kevin Sookocheff]

Thanks Sumil.

Does anyone know what algorithm they are implementing? It looks like a wheel factorization but I can't tell from lack ofcomments.

[Justin Kramer]

See also David Nolan's post:

http://dosync.posterous.com/lispers-know-the-value-of-everything-and-the

Justin

[Kevin Sookocheff]

Thanks Justin, this is a terrific implementation.