code-reviews 2022-03-19 | Slack Archive

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

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

JoshLemer16:03:35

Interesting

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:54

Dang!

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:39

@joshlemer ^

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.

2022-03-19

Channels