Re: Creating a map algorithmically
Thanks Justin, this is a terrific implementation. -- 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
Re: Creating a map algorithmically
See also David Nolan's post: http://dosync.posterous.com/lispers-know-the-value-of-everything-and-the Justin On Tuesday, August 9, 2011 6:02:00 PM UTC-4, pmbauer wrote: > > 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 >> 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
Re: Creating a map algorithmically
Thanks Sumil. Does anyone know what algorithm they are implementing? It looks like a wheel factorization but I can't tell from lack ofcomments. -- 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
Re: Creating a map algorithmically
you should considering looking at clojure.contrib.lazy-seqs/primes to get an idea it is implemented there.. Sunil. On Wed, Aug 10, 2011 at 1:48 AM, Chouser wrote: > On Tue, Aug 9, 2011 at 12:50 PM, Kevin Sookocheff > 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 > -- 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
Re: Creating a map algorithmically
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 > 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
Re: Creating a map algorithmically
On Tue, Aug 9, 2011 at 12:50 PM, Kevin Sookocheff 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
Re: Creating a map algorithmically
(zipmap (range 2 (inc n)) (repeat true)) -- 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
Re: Creating a map algorithmically
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
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.
>
> 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
--
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
Creating a map algorithmically
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. 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 -- 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
