I have updated my Lucky Numbers code:
(defn indexed-sieve
"Removes all elements that have a position that is a multiply of
index.
With first position counting as 1."
[index this-list]
(keep-indexed
(fn [i v]
(if (= 0 (mod (inc i) index))
nil
v))
this-list))
; current-list of Integer instead of default Double makes the code
little more efficient
; using reduce would make neater code (no need for atoms),
; but gives a stack-overflow for 18.000 and takes about twice as long
(defn lucky-numbers
; doc-string contains max-value
"Lucky numbers from 1 up-to upto-value.
1 <= upto-value <= 10.000.000
http://en.wikipedia.org/wiki/Lucky_number";
[upto-value]
; max-value is also used in doc-string
(let [max-value (int 1e7)]
(when (< upto-value 1)
(throw (Exception. "ERROR: upto-value should at least be 1")))
(when (> upto-value max-value)
(throw (Exception. (format "ERROR: upto-value greater then %d"
max-value))))
(let [current-list (atom (indexed-sieve 2 (range (int 1) (int
upto-value))))
current-index (atom 1)]
(while (< @current-index (count @current-list))
(reset! current-list (indexed-sieve (nth @current-list
@current-index) @current-list))
(reset! current-index (inc @current-index)))
@current-list)))
Code has become a little bit bigger, but it checks some preconditions now
also.
Is this the good way to document things?
One problem is that max-value is used in the doc-string also, so if it
changes, it has to be done at two places. Is there a way around this?
When running:
(for [i (range 1 (inc 6))]
(do
(time
(let [upto (int (Math/pow 10 i))]
(def lucky (lucky-numbers upto))
(printf "With upto %d there are %d lucky numbers\n" upto (count
lucky))))
(printf "\n")))
You get on my system:
(With upto 10 there are 4 lucky numbers
"Elapsed time: 0.622653 msecs"
With upto 100 there are 23 lucky numbers
"Elapsed time: 0.295401 msecs"
With upto 1000 there are 153 lucky numbers
"Elapsed time: 5.516305 msecs"
With upto 10000 there are 1118 lucky numbers
"Elapsed time: 211.366758 msecs"
With upto 100000 there are 8772 lucky numbers
"Elapsed time: 12166.737039 msecs"
With upto 1000000 there are 71918 lucky numbers
"Elapsed time: 888851.623386 msecs"
nil nil nil nil nil nil)
So I think the max-value of 10.000.000 should not be increased. (Maybe
decreased.) If max-value is used I think it will take 15 hours to a day to
compute.
By the way the reduce version that is slower and does not work with a
max-value of 18.000:
(defn drop-nth [n coll]
(lazy-seq
(when-let [s (seq coll)]
(concat (take (dec n) s) (drop-nth n (drop n s))))))
(defn lucky-fn
"Returns sequence of Lucky numbers less than max"
([max] (when (pos? max) (lucky-fn 1 (range 1 max 2))))
([i acc]
(if-let [n (nth acc i nil)]
(recur (inc i) (drop-nth n acc))
acc)))
If someone knows a way to get a reduce version that gets near the atom
version …
--
Cecil Westerhof
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
