0
\$\begingroup\$

This code to solve Problem 23 in Project Euler gives the 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 +))
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Thank you for the time and suggestions. With filterv, my running time comes down to 17 seconds. Great find! If I wanted to figure out what's the reason for the difference between the two versions, how should I go about it? \$\endgroup\$ – nakiya Nov 7 '18 at 2:39
  • 1
    \$\begingroup\$ @nakiya Profile it and see where the time is being spent, what's using memory, and what the GC is doing. filter might be using more memory, which is causing the GC to run too often. VisualVM comes with the JDK, and is available for free from the Java site. It's not perfect, but it's been pretty helpful for me. \$\endgroup\$ – Carcigenicate Nov 7 '18 at 2:44
  • 1
    \$\begingroup\$ I found that by removing the whole sub-ab calc and by simply using abundants instead or sub-ab in is-sum-of-two-abundants?, I can reduce running time to 2 seconds. i.e (defn is-sum-of-two-abundants? [num] (some (fn [ab] (abundants (- num ab))) abundants)) \$\endgroup\$ – nakiya Nov 7 '18 at 3:13
  • \$\begingroup\$ @nakiya That's because that gets rid of all the end filtering. Was (filterv #(< % num)) never necessary in the first place? I honestly didn't look into the algorithm itself in too much detail. \$\endgroup\$ – Carcigenicate Nov 7 '18 at 3:19
1
\$\begingroup\$

I've just noticed that this answer is anticipated by @Nakiya's comments on @Carciginate's answer. I'll leave it up, since it explains things more fully and does go a little further.


There is a single change that makes your algorithm run about twenty times faster, dropping the time taken from about thirty seconds to between one and two seconds.

Look at your is-sum-of-two-abundants? function:

(defn is-sum-of-two-abundants? [num]
  (let [sub-ab (->> abundants
                    (filterv #(< % num))
                    (set))]
    (some (fn [ab]
            (sub-ab (- num ab)))
          sub-ab)))

You build a new sub-ab set every time. And you scan the whole of the abundants set to do so. You do this for every number you test. So the time this takes is of the order of (* LIMIT (count abundants)), where ...

(def LIMIT 28123)

Let's construct the abundants as a sequence, and - from that - as a set:

(def abundants-seq
  (->> (range 12 LIMIT)
       (map #(vector % (sum-div %)))
       (filter #(> (second %) (first %)))
       (map first)))

(def abundants-set (set abundants-seq))
  • We can use the whole abundants-set, created once and for all, to test for the presence of any one of them. This takes more or less constant time, regardless of how big the set is.
  • Since the abundants-seq is in increasing order, we can just stop when the numbers get too big.

This gives us

(defn is-sum-of-two-abundants? [num]
  (let [sub-ab (take-while #(< % num) abundants-seq)]
    (some (fn [ab]
            (abundants-set (- num ab)))
      sub-ab)))

I've kept the name sub-ab for the candidates, as a sequence, not a set.

So that we can time it, I've made the final calculation into a function:

(defn answer []
  (->> (range (inc LIMIT))
       (remove is-sum-of-two-abundants?)
       (reduce +)))

... taking the chance to elide (filter (complement ... ) ... into (remove ... ....

Timings

Before

user=> (time (let [x (answer)] (println x)))
4179871
"Elapsed time: 29488.662721 msecs"

After

user=> (time (let [x (answer)] (println x)))
4179871
"Elapsed time: 1646.560626 msecs"

The work of constructing abundants-seq and abundants-set is done at compile/load time. The former can be done far faster too, as this related discussion describes. However, this is not the dominant phase here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.