Skip to main content
Code Review

Return to Answer

a little clearer
Source Link
Thumbnail
Thumbnail
  • 1.6k
  • 9
  • 16

I've played around with your code to try to understand it, frankly. After a long sequence of changes, I ended up with the following:

(defn primes [n]
  (let [mark (fn [i di v]
               (reduce
                 (fn [v-[w i] (assoc v-w i di))
                 v
                 (range i (count v) di)))
        complete[answer &_] (reduce
                      (fn [[ps v :as both] i]
                        (if (= (v i) 1)
                          [(conj ps i) (mark (* i i) i v)]
                          both))
                      (let [init-v (->> (repeat 1) (take n) (vec))]
                        [[] init-v])
                      (range 2 n))]
    (first complete)answer))
  • I've got rid of the decs in all yourthe accesses to the vector v.
  • I've captured yourthe recurs, both in the mark and step functions, in reduces.
  • Since the step function is no longer recursive, I've unwrapped it into its one call.

The new mark function is, I think, a little faster. But the step equivalent is probablygoing to be slower, since it generates a new vectorpair-pairvector for every prime.

I'd imagine theThe main problem here is space - your vector v is the size of your candidate range of numbers. I've come across a cute algorithm that gets round this, though at some cost in speed, spent on laziness.

I've played around with your code to try to understand it, frankly. After a long sequence of changes, I ended up with the following:

(defn primes [n]
  (let [mark (fn [i di v]
               (reduce
                 (fn [v- i] (assoc v- i di))
                 v
                 (range i (count v) di)))
        complete (reduce
                   (fn [[ps v :as both] i]
                     (if (= (v i) 1)
                       [(conj ps i) (mark (* i i) i v)]
                       both))
                   (let [init-v (->> (repeat 1) (take n) (vec))]
                     [[] init-v])
                   (range 2 n))]
    (first complete)))
  • I've got rid of the decs in all your accesses to the vector v.
  • I've captured your recurs, both in the mark and step functions, in reduces.
  • Since the step function is no longer recursive, I've unwrapped it into its one call.

The new mark function is, I think, a little faster. But the step equivalent is probably slower, since it generates a new vector-pair for every prime.

I'd imagine the main problem here is space - your vector v the size of your candidate range of numbers. I've come across a cute algorithm that gets round this, though at some cost in speed, spent on laziness.

I've played around with your code to try to understand it, frankly. After a long sequence of changes, I ended up with the following:

(defn primes [n]
  (let [mark (fn [i di v]
               (reduce
                 (fn [w i] (assoc w i di))
                 v
                 (range i (count v) di)))
        [answer &_] (reduce
                      (fn [[ps v :as both] i]
                        (if (= (v i) 1)
                          [(conj ps i) (mark (* i i) i v)]
                          both))
                      (let [init-v (->> (repeat 1) (take n) (vec))]
                        [[] init-v])
                      (range 2 n))]
    answer))
  • I've got rid of the decs in all the accesses to the vector v.
  • I've captured the recurs, in the mark and step functions, in reduces.
  • Since the step function is no longer recursive, I've unwrapped it into its one call.

The new mark function is a little faster. But the step equivalent is going to be slower, since it generates a new pair-vector for every prime.

The main problem here is space - your vector v is the size of your candidate range of numbers. I've come across a cute algorithm that gets round this, though at some cost in speed, spent on laziness.

Source Link
Thumbnail
Thumbnail
  • 1.6k
  • 9
  • 16

I've played around with your code to try to understand it, frankly. After a long sequence of changes, I ended up with the following:

(defn primes [n]
  (let [mark (fn [i di v]
               (reduce
                 (fn [v- i] (assoc v- i di))
                 v
                 (range i (count v) di)))
        complete (reduce
                   (fn [[ps v :as both] i]
                     (if (= (v i) 1)
                       [(conj ps i) (mark (* i i) i v)]
                       both))
                   (let [init-v (->> (repeat 1) (take n) (vec))]
                     [[] init-v])
                   (range 2 n))]
    (first complete)))
  • I've got rid of the decs in all your accesses to the vector v.
  • I've captured your recurs, both in the mark and step functions, in reduces.
  • Since the step function is no longer recursive, I've unwrapped it into its one call.

The new mark function is, I think, a little faster. But the step equivalent is probably slower, since it generates a new vector-pair for every prime.

I'd imagine the main problem here is space - your vector v the size of your candidate range of numbers. I've come across a cute algorithm that gets round this, though at some cost in speed, spent on laziness.