This page is not created by, affiliated with, or supported by Slack Technologies, Inc.

## 2022-03-19

## Channels

- # aleph (9)
- # announcements (1)
- # asami (21)
- # aws (1)
- # babashka (4)
- # babashka-sci-dev (95)
- # beginners (35)
- # calva (27)
- # cider (17)
- # cljsrn (1)
- # clojure-europe (8)
- # clojure-norway (1)
- # clojuredesign-podcast (4)
- # clojurescript (18)
- # code-reviews (28)
- # core-logic (1)
- # cursive (3)
- # datalevin (2)
- # holy-lambda (3)
- # honeysql (1)
- # introduce-yourself (11)
- # kaocha (12)
- # lsp (11)
- # malli (9)
- # off-topic (46)
- # polylith (16)
- # re-frame (3)
- # reitit (2)
- # releases (2)
- # tools-deps (9)
- # web-security (1)
- # xtdb (2)

Thanks @noisesmith

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
}
```

```
(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))))
```

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

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`

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

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))))
```

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

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

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.

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

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

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

Thanks for the update @noisesmith