Cecil Westerhof <cldwester...@gmail.com> writes:
> 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?
I wouldn't specify a max-value at all. Some users might have enough
time to wait for the result, have faster machines, might use the
function in some years in the future where we all have faster
machines...
> 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 …
Here's my version:
--8<---------------cut here---------------start------------->8---
(defn drop-every-nth [c n]
(keep-indexed (fn [i el]
(if (zero? (mod (inc i) n)) nil el))
c))
(defn lucky-numbers [n]
(loop [c (range 1 (inc n) 2), survivor-idx 1]
(let [i (nth c survivor-idx)]
(if (> (count c) i)
(recur (drop-every-nth c i) (inc survivor-idx))
c))))
--8<---------------cut here---------------end--------------->8---
Runtimes of that version:
--8<---------------cut here---------------start------------->8---
user> (lucky-numbers 100)
(1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99)
user> (time (dorun (lucky-numbers 100)))
"Elapsed time: 0.079083 msecs"
nil
user> (time (dorun (lucky-numbers 1000)))
"Elapsed time: 0.690399 msecs"
nil
user> (time (dorun (lucky-numbers 100000)))
"Elapsed time: 1023.293714 msecs"
nil
user> (time (dorun (lucky-numbers 1000000)))
"Elapsed time: 63413.245417 msecs"
nil
--8<---------------cut here---------------end--------------->8---
That version is about a factor of 10 times faster than your version on
my system (which I renamed to lucky-numbers-cecil):
--8<---------------cut here---------------start------------->8---
(time (dorun (lucky-numbers-cecil 100)))
"Elapsed time: 0.234188 msecs"
nil
user> (time (dorun (lucky-numbers-cecil 1000)))
"Elapsed time: 6.457705 msecs"
nil
user> (time (dorun (lucky-numbers-cecil 100000)))
"Elapsed time: 10017.472552 msecs"
nil
user> (time (dorun (lucky-numbers-cecil 1000000)))
;; I waited for more than 10 minutes before aborting...
--8<---------------cut here---------------end--------------->8---
Since our two versions are almost identical from an algorithmical point
of view, the slowdown of your version seems to be caused entirely by the
overhead of atoms.
The other version you cite above can also be fixed so that it doesn't
overflow the stack so early:
--8<---------------cut here---------------start------------->8---
(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]
(let [n (nth acc i)]
(if (> (count acc) n)
(recur (inc i) (drop-nth n acc))
acc))))
--8<---------------cut here---------------end--------------->8---
The fix is that the recursion only takes place if n is smaller than the
collection size. This cuts off a lot of drop-nth invocations that
actually do nothing because ,e.g., (drop-nth (1 3 7 9 13) 7) is a no-op
because there is no index 7 anyway.
This version is also faster than your version but a bit slower than my
version:
--8<---------------cut here---------------start------------->8---
user> (time (dorun (lucky-fn 100)))
"Elapsed time: 0.626644 msecs"
nil
user> (time (dorun (lucky-fn 100)))
"Elapsed time: 0.174697 msecs"
nil
user> (time (dorun (lucky-fn 1000)))
"Elapsed time: 2.844104 msecs"
nil
user> (time (dorun (lucky-fn 1000)))
"Elapsed time: 2.1722 msecs"
nil
user> (time (dorun (lucky-fn 100000)))
"Elapsed time: 2481.224451 msecs"
nil
--8<---------------cut here---------------end--------------->8---
Bye,
Tassilo
--
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 unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
