Nsryjdtyk

So, this code to solve Problem 23 in Project Euler (https://projecteuler.net/problem=23) gives correct answer. But, running the last expression takes around 40 seconds.

I welcome advice on how to improve performance here.

(defn sum-div [num]

  (->> (range 2 (+ 1 (int (Math/ceil (Math/sqrt num)))))

       (filter #(= (mod num %) 0))

       (map (fn [x]

              (let [d (/ num x)]

                (if (= x d)

                  x

                  [x d]))))

       flatten

       distinct

       (reduce +)

       (+ 1)))



(def abundants

  (->> (range 12 28123)

       (map #(vector % (sum-div %)))

       (filter #(> (second %) (first %)))

       (map first)

       set))



(defn is-sum-of-two-abundants?

  [num]

  (let [sub-ab (->> abundants

                    (filter #(< % num))

                    set)]

    (some (fn [ab]

            (sub-ab (- num ab)))

          sub-ab)))



(->> (range 28124)

     (filter (complement is-sum-of-two-abundants?))

     (reduce +))

I played around with this for a good half hour without any luck. I was consistently getting ~57 seconds on my crappy M3 laptop.

As a last ditch effort though, I changed

(->> abundants

     (filter #(< % num))

     set)

to

(->> abundants

     (filterv #(< % num)) ; Note the v

     set)

And got it down to 25 seconds! Since you seem to be using a faster computer than me, you'll likely get an even lower time.

Why does this cause such a dramatic change? ¯_(ツ)_/¯. filterv is strict while filter is lazy, but I have no idea why that makes such a difference here. I would have expected it to be slower since the strict filtering would require a full iteration on its own, then the adding to the set would require another full iteration. Apparently something else is going on. I'll update this answer if I think of what may be happening.

I cleaned up the code a bit too, although none of the other changes made any performance impact. These are mostly just personal stylistic and practice recommendations. See the comments:

(def lower-limit 12) ; Defining these so they aren't magic,

(def upper-limit 28123) ; especially since upper-limit is used in two places



(defn sum-div [num]

  (->> (range 2 (inc (int (Math/ceil (Math/sqrt num)))))

       (filter #(= (mod num %) 0))

       (map (fn [x]

              (let [d (/ num x)]

                (if (= x d)

                  x

                  [x d]))))

       (flatten) ; I personally prefer wrapping for consistency

       (distinct)

       (apply +) ; apply is generally regarded as more idiomatic for summing

       (inc))) ; Use inc instead of (+ 1)



(def abundants

  (->> (range lower-limit upper-limit)

       (map #(vector % (sum-div %)))

       (filter #(> (second %) (first %)))

       (map first)

       (set)))



(defn is-sum-of-two-abundants?

  [num]

  (let [sub-ab (->> abundants

                    (filterv #(< % num))

                    (set))]

    (some (fn [ab]

            (sub-ab (- num ab)))

          sub-ab)))



(time

  (->> (range (inc upper-limit)) ; Use upper limit

       (remove is-sum-of-two-abundants?) ; remove is literally equal to (filter (complement ...))

       (apply +)))



"Elapsed time: 26714.867469 msecs"

=> 4179871