Five functions to get the digits of a number

Question

I'm writing a simple function: given a number, it will return a sequence or a collection of the digits in the number (in the correct order). i.e (get-digits-fn 1234567) => (1 2 3 4 5 6 7) / [1 2 3 4 5 6 7]

Below are five attempts at the same function:

(defn get-digits-1 [num]
  (->> [num '()]
       (iterate (fn [[num digits]]
                  (when (> num 0)
                    [(quot num 10) (conj digits (rem num 10))])))
       (take-while some?)
       (last)
       (second)))

(defn get-digits-2 [num]
  (when (> num 0)
    (lazy-seq (concat (get-digits-2 (quot num 10)) '((rem num 10))))))

;; Suggested by Carcigenate
(defn get-digits-3 [num]
  (->> (str)
       (map str)
       (map int)
       (into '())))

(defn get-digits-4 [num]
  (loop [n num
         res '()]
    (if (= n 0)
      res
      (recur (quot n 10) (conj res (rem n 10))))))

(defn get-digits-5 [num]
  (->>
   (iterate (fn [[n digits]]
              [(quot n 10) (conj digits (rem n 10))])
            [num '()])
   (drop-while #(not= 0 (first %)))
   (first)
   (second)))

A helper function for testing performance:

(defn quick-bench-get-digits [fn range]
  (quick-bench (->> range
                    (map fn)
                    (map (partial apply vector))
                    (into []))))

The perf results (output truncated to only show execution time mean):

eul> (quick-bench-get-digits get-digits-1 (range 1 100000))
Execution time mean : 129.516521 ms

eul> (quick-bench-get-digits get-digits-2 (range 1 100000))
Execution time mean : 128.637055 ms

eul> (quick-bench-get-digits get-digits-3 (range 1 100000))
Execution time mean : 24.267716 ms

eul> (quick-bench-get-digits get-digits-4 (range 1 100000))
Execution time mean : 25.083393 ms

eul> (quick-bench-get-digits get-digits-5 (range 1 100000))
Execution time mean : 145.430443 ms

It looks like get-digits-3 is the fastest while get-digits-4 is closely behind. (As the numbers increase, get-digits-3 outperforms get-digits-4. i.e try (range 1000000 2000000))

Any way to increase performance more without leaving Clojure land?
If mutability and Java inter-op is allowed, is there a way to increase performance?

p.s. functions 1 and 5 are almost identical. This was incremental exploration.

Is performance of this code specifically really a concern? I'm doubtful that this is what would be the choking point of the program. 24ms is very fast, especially for an inflated test case. — Carcigenicate
– Carcigenicate, Commented Nov 9, 2018 at 17:59

Thumbnail · Accepted Answer · 2019-01-12 22:43:02Z

I'm afraid your code has errors, so your benchmarking is invalid.

The get-digits-3 function is wrong.
A corrected version runs about twelve times slower than get-digits-4.

Repairing get-digits-3

Your get-digits-3 doesn't work:

=> (get-digits-3 123456789)
()

The function chain should be applied to the argument num:

(defn get-digits-3 [num]
  (->> num
       (str)
       (map str)
       (map int)
       (into '())))

But this fails:

=> (get-digits-3 123456789)
ClassCastException java.base/java.lang.String cannot be cast to java.base/java.lang.Character  clojure.lang.RT.intCast (RT.java:1213)

The culprit is the (map int) line. You can't apply int to strings. If you drop the offending line, you get the character values:

=> (get-digits-3 123456789)
(57 56 55 54 53 52 51 50 49)

Notice, too, that they are in reverse order. So we

subtract the value of character 0 and
conj onto the other end by using a vector.

This gives us ...

(defn get-digits-3 [num]
  (->> num
       (str)
       (map int)
       (map #(- % (int \0)))
       (into [])))

=> (get-digits-3 123456789)
[1 2 3 4 5 6 7 8 9]

Benchmarking

I went about this differently:

I used a single example instead of a range.
I used Criterium's bench rather than its quick-bench.

The results were as follow:

For your original (faulty) version of get-digits-3:

=> (bench (get-digits-3 123456789))
...
             Execution time mean : 228.998292 ns

For the corrected version:

=> (bench (get-digits-3 123456789))
...
             Execution time mean : 3.440024 µs

And for get-digits-4:

=>(bench (get-digits-4 123456789))
...
             Execution time mean : 247.502418 ns

This confirms that your faulty get-digits-3 is about as fast as get-digits-4. And get-digits-3 ignores its argument, so is bound to get relatively faster as the numbers get bigger. You can see that the corrected version is nowhere near competitive.

Stack Exchange Network

Five functions to get the digits of a number

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Five functions to get the digits of a number

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions