Fork me on GitHub
#code-reviews
<
2022-03-19
>
JoshLemer19:03:30

Doing some practice problems on leetcode (they don't support clojure but I translate in editor) I wonder if anyone could simplify my Roman Numerals solution to be even smaller/simpler without sacrificing performance

``````(def magnitudes {\I 1
\V 5
\X 10
\L 50
\C 100
\D 500
\M 1000})

(defn roman-numerals [s]
(loop [str (reverse s)
result 0
max-magnitude -1]
(if (empty? str)
result
(let [c (first str)
magnitude (magnitudes c)]
(if
(>= magnitude max-magnitude)
(recur (rest str) (+ result magnitude) magnitude)
(recur (rest str) (- result magnitude) max-magnitude))))))

;; test cases
(doseq [[input expected] [["III" 3] ["LVIII" 58] ["MCMXCIV" 1994]]]
(let [actual (roman-numerals input)]
(assert (= (roman-numerals input) expected)
{:input input :expected expected :actual actual})))``````
I am comparing to the equivalent solution in Go and there it is possible to get smaller because with the `range` control structure you don't have to explicitly check for the end of the loop like in the clojure solution checking `(empty? str)`, and don't have to explicitly pass `(rest str)` to next iteration:
``````var Magnitudes map[rune]int = map[rune]int{
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}

func RomanNumerals(s string) (result int) {
maxMagnitude := -1
runes := []rune(s)
for i := range runes {
r := runes[len(runes)-i-1]
magnitude := Magnitudes[r]
if magnitude >= maxMagnitude {
result += magnitude
maxMagnitude = magnitude
} else {
result -= magnitude
}
}
return
}``````

potetm22:03:20

``````(def magnitudes {\I 1
\V 5
\X 10
\L 50
\C 100
\D 500
\M 1000})

(defn roman-numerals [s]
(second (reduce (fn [[mx res] c]
(let [m (magnitudes c)]
(if (<= mx m)
[m (+ res m)]
[mx (- res m)])))
[-1 0]
(clojure.string/reverse s))))``````

❤️ 1 1
JoshLemer16:03:23

Thanks for this, I considered using reduce but decided against since it ends up incurring a O(n) cost in terms of allocating all these `[m (+ res m)]` etc vectors

potetm16:03:53

My solution is faster than yours.

potetm16:03:11

running the following at 100k invocations:

``````(roman-numerals "III")
(roman-numerals "IV")
(roman-numerals "LVIII")
(roman-numerals "MCMXCIV")``````
My solution averages `2470.76227 ns` and yours averages `2902.8878 ns`

potetm17:03:03

The difference is apparently entirely inside the `reverse` invocation.

potetm17:03:19

Changing yours to `clojure.string/reverse` brings them both to parity.

potetm17:03:39

tl;dr allocation isn’t as expensive as you think, and the operation is O(n) no matter what

JoshLemer17:03:08

worth noting that use of maps for the reduction is quite a bit more expensive (unfortunate, since it's arguably more comprehensible etc)

``````(defn roman-numerals [s]
(second (reduce (fn [{:keys [mx res]} c]
(let [m (magnitudes c)]
(if (<= mx m)
{:mx m :res (+ res m)}
{:mx mx :res (- res m)})))
{:mx -1 :res 0}
(clojure.string/reverse s))))``````

JoshLemer17:03:26

(like twice as much execution time)

potetm17:03:08

I’m only getting about a 50% increase at 100k invocations, but yeah maps are generally more expensive.

potetm17:03:56

I’m not exactly sure why — perhaps because you they can have arbitrary keys, so lookups have to do more work?

JoshLemer17:03:08

Well there's a lot more stuff to do both in constructing and in doing lookups in maps. Keys have to be hashed, there's some bitwise stuff going on to place key-value pairs in buckets, there's twice the allocation.

potetm18:03:36

p sure keys are still hashed in clojure vectors

potetm18:03:46

they’re both backed by tries

potetm18:03:08

again, I’m no expert on clojure data structure implementations. Could be wrong.

noisesmith18:03:30

@U07S8JGF7 in a vector, the key is just index? no hashing needed

noisesmith18:03:31

vectors are not backed by a hash map, vectors and hash maps are both backed by tries, but the one for vectors can make a number of optimizations that come from the keys being integers that are contiguous

noisesmith18:03:21

also, there's an optimization for small vectors that just uses an array

potetm18:03:56

Yeah I kinda figured as much after thinking about it a little more.

potetm18:03:14

Thanks for the update @noisesmith

potetm22:03:30

fwiw, you would usually do:

``````(ns my.ns
(:require
[clojure.string :as str]))``````

potetm22:03:38

And then use `(str/reverse s)`

potetm22:03:56

I just put the full name so you would know what it is.