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.
