3
\$\begingroup\$

I solved LC12 (Integer to Roman) in Rust.

I am a beginner with Rust, so I translated my previous solution from C++ to Rust. I am looking for feedback on how I could improve the following Rust code.

The make_digit is nested because I got error saying it's not available in the current scope.

I could find the following cases:

  • thousands: just add M for how many thousands are in the number;
  • non-thousand digit:
    • 9: <Digit_1><Digit_10> (c1 and c10 in the code)
    • 4: <Digit_1><Digit_5>
    • 5 --> 8: <Digit_5><Digit_1 * digit % 5>
    • 1 --> 3: <Digit_1 * digit>

where Digit_1 is the lowest digit in the group (I, X, C) Digit_5: V, L, D Digit_10: X, C, M

impl Solution {
    pub fn int_to_roman(num: i32) -> String {  
        pub fn make_digit(digit: i32, c10: char, c5: char, c1: char) -> String {
            let mut res = "".to_string();
            if (digit == 9){
                res.push(c1);
                res.push(c10);
            }
            else if (digit >= 5){
                res.push(c5);
                for ii in 0..(digit - 5) {
                    res.push(c1);
                }
            }
            else if (digit == 4){
                res.push(c1);
                res.push(c5);
            }
            else 
            {
                for ii in 0..digit{
                    res.push(c1);
                }
            }
            return res;
        } // make_digit
        
        let mut ncopy = num;
        let thousands: i32 = num / 1000;
        let mut result: String = "".to_string();
        for ii in 0..thousands {
            result.push('M');
        }
        
        ncopy %= 1000;
        
        let mapping = std::collections::HashMap::from([
            (1000, 'M'),
            (500, 'D'),
            (100, 'C'),
            (50, 'L'),
            (10, 'X'),
            (5, 'V'),
            (1, 'I'),
        ]);
        
        let mut modulo = 100;
        while modulo >= 1 {
            let digit = ncopy / modulo;
            // println!("Modulo: {modulo}");
            result += &make_digit(digit, mapping[&(modulo * 10)], mapping[&(modulo * 5)], mapping[&modulo]);
            ncopy %= modulo;
            modulo /= 10;
            
        }
        return result;
    }
}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Right now, you use a combination of two techniques to solve the problem, when either would be simpler and more efficient by itself: a local helper function, and a lookup table.

The local helper could be a tail-recursive function with two parameters, an accumulator and a residue. Here’s a simple but verbose implementation, which takes advantage of the fact that local variables in Rust use move semantics. I use .push() as you do, but the Rust String and str& types support the + and += operators, which also re-use the buffer if possible.

pub fn int_to_roman(num: i32) -> String {
    fn helper( mut numerals : String, residue : i32 ) -> String {
        if residue >= 4000 {
            String::from("Too Large")
        } else if residue >= 1000 {
            numerals.push('M');
            helper(numerals, residue - 1000)
        } else if residue >= 900 {
            numerals.push('C');
            numerals.push('M');
            helper(numerals, residue - 900)
        } else if residue >= 500 {
            numerals.push('D');
            helper(numerals, residue - 500)
        } else if residue >= 400  {
            numerals.push('C');
            numerals.push('D');
            helper(numerals, residue - 400 )
        } else if residue >= 100 {
            numerals.push('C');
            helper(numerals, residue - 100 )
        } else if residue >= 90 {
            numerals.push('X');
            numerals.push('C');
            helper(numerals, residue - 90)
        } else if residue >= 50 {
            numerals.push('L');
            helper(numerals, residue - 50)
        } else if residue >= 40 {
            numerals.push('X');
            numerals.push('L');
            helper(numerals, residue - 40)
        } else if residue >= 10 {
            numerals.push('X');
            helper(numerals, residue - 10)
        } else if residue >= 9 {
            numerals.push('I');
            numerals.push('X');
            helper(numerals, residue - 9)
        } else if residue >= 5 {
            numerals.push('V');
            helper(numerals, residue - 5)
        } else if residue >= 4 {
            numerals.push('I');
            numerals.push('V');
            helper(numerals, residue - 4)
        } else if residue >= 1 {
            numerals.push('I');
            helper(numerals, residue - 1)
        } else if residue == 0 {
            numerals
        } else {
            String::from("Too Small")
        }
    }
    
    return helper( String::from(""), num )
}

To get an idea of the efficiency of this code, let’s examine the output of one of the else if blocks from Godbolt:

else if residue >= 1000 {
            numerals.push('M');
            helper(numerals, residue - 1000)
        }

With -O, this compiles to:

        cmp     edx, 999
        jle     .LBB7_2
        mov     rsi, qword ptr [rbx + 16]
        cmp     rsi, qword ptr [rbx + 8]
        jne     .LBB7_22
        mov     rdi, rbx
        call    alloc::raw_vec::RawVec<T,A>::reserve_for_push
        mov     rsi, qword ptr [rbx + 16]
.LBB7_22:
        mov     rax, qword ptr [rbx]
        mov     byte ptr [rax + rsi], 77
        add     rsi, 1
        mov     qword ptr [rbx + 16], rsi
        mov     rax, qword ptr [rbx + 16]
        mov     qword ptr [rsp + 16], rax
        movups  xmm0, xmmword ptr [rbx]
        movaps  xmmword ptr [rsp], xmm0
        add     ebp, -1000
        jmp     .LBB7_43

You will notice there is no modular arithmetic, only comparisons and subtractions.

The first half of this checks the capacity of the String and enlarges if necessary. As you can see, the part that updates the string and calls helper tail-recursively is reasonably efficient (it misses an opportunity to optimize by updating numerals in place, but an alternative would be to declare numerals within the scope of int_to_roman and passing it between calls to helper by mutable reference), and takes advantage of Rust’s default move semantics for passing mut arguments to a function call. Thus, it uses both copy elision and tail-call elimination. (You could do the same in C++, but you would need to pass std::move(numerals). In Rust, this is the default for a mut parameter.)

You could improve on the code above, but I’ll let you decide how. Here are a couple of ideas. If you store pairs like (1000,"M") in a dictionary, you can test each value in the dictionary, from highest to lowest, and append the representation of each value that matches to your numeral. If you remember your place in the dictionary, the code not only becomes more readable, but can avoid double-checking numerals it’s already eliminated.

It is, however, possible to do better, with branchless code. You calculate the individual digits and make use of a hash map between values and numerals. You could instead look up each digit in an array, in constant time, and concatenate the results for all digits.

pub fn int_to_roman(num: i32) -> String {
  let raw = num as usize;
  let thousands = raw % 10000 / 1000;
  let hundreds = raw % 1000 / 100;
  let tens = raw % 100 / 10;
  let ones = raw % 10;

  static THOUSANDS_ENCODING : [&str; 10] =
    ["", "M", "MM", "MMM", "?", "?", "?", "?", "?", "?"];

  static HUNDREDS_ENCODING : [&str; 10] =
    ["", "C", "CC", "CCC", "CD", "D",  "DC", "DCC", "DCCC", "CM"];

  static TENS_ENCODING : [&str; 10] =
    ["", "X", "XX", "XXX", "XL","L", "LX", "LXX", "LXXX", "XC"]; 

  static ONES_ENCODING : [&str; 10] =
    ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];

  return THOUSANDS_ENCODING[thousands].to_string() +
         HUNDREDS_ENCODING[hundreds] +
         TENS_ENCODING[tens] +
         ONES_ENCODING[ones]
}

(I earlier gave a much worse implementation.) This version uses static, immutable lookup tables of string slices for efficiency: the compiler does not need to do any initialization of these at runtime. The first term of the string concatenation is converted .to_string(), to obtain a temporary String that can be appended to. This is then returned with copy elision. The function needs to do a type cast at the top, because array indices in Rust have type usize, and the language will not accept a signed subscript.

This code is approximately equivalent to concatenating values from constexpr std::string_view[] tables in C++.

There are faster solutions out there, which for example iterate over the reversed decimal digits of the input rather than doing modular arithmetic.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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