я решил LC12 (целое число в латинское) в Русте.
Я новичок в Rust, поэтому я перевел свое предыдущее решение с C++ на Rust. Я ищу отзывы о том, как я могу улучшить следующий код Rust.
make_digit является вложенным, потому что я получил сообщение об ошибке, говорящее, что он недоступен в текущей области.
Я смог найти следующие случаи:
- тысячи: просто добавьте M, чтобы узнать, сколько тысяч в числе;
- нетысячная цифра:
- 9: <Цифра_1><Цифра_10> (
c1а такжеc10в коде) - 4: <Цифра_1><Цифра_5>
- 5 —> 8:
- 1 —> 3: <цифра_1 * цифра>
- 9: <Цифра_1><Цифра_10> (
где Цифра_1 — самая младшая цифра в группе (I, X, C) Цифра_5: V, L, D Цифра_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;
}
}
Мирча
1 ответ
Прямо сейчас вы используете комбинацию двух методов для решения проблемы, когда любой из них сам по себе был бы проще и эффективнее: локальная вспомогательная функция и таблица поиска.
Локальный помощник может быть хвостовой рекурсивной функцией с двумя параметрами, аккумулятором и остатком. Вот простая, но многословная реализация, которая использует тот факт, что локальные переменные в Rust используют семантику перемещения. я использую .push() как и ты, но ржавчина String а также str& типы поддерживают + а также += операторы, которые также повторно используют буфер, если это возможно.
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 )
}
Чтобы получить представление об эффективности этого кода, давайте рассмотрим вывод одного из else if блоки от Godbolt:
else if residue >= 1000 {
numerals.push('M');
helper(numerals, residue - 1000)
}
С -Oэто компилируется в:
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
Вы заметите, что здесь нет модульной арифметики, только сравнения и вычитания.
Первая половина этого проверяет емкость String и увеличивается при необходимости. Как видите, та часть, которая обновляет строку и вызывает helper tail-recursive достаточно эффективен (он упускает возможность оптимизировать, обновляя numerals на месте, но альтернативой было бы объявить numerals в рамках int_to_roman и передавать его между вызовами helper по изменяемой ссылке) и использует стандартную семантику перемещения Rust для передачи mut аргументы вызова функции. Таким образом, он использует как исключение копирования, так и исключение хвостового вызова. (Вы могли бы сделать то же самое на C++, но вам нужно было бы передать std::move(numerals). В Rust это значение по умолчанию для mut параметр.)
Вы можете улучшить приведенный выше код, но я позволю вам решить, как это сделать. Вот несколько идей. Если вы храните такие пары, как (1000,"M") в словаре вы можете проверить каждое значение в словаре, от самого высокого до самого низкого, и добавить представление каждого значения, которое соответствует вашему числу. Если вы помните свое место в словаре, код не только становится более читаемым, но и позволяет избежать повторной проверки числительных, которые он уже исключил.
Однако можно добиться большего успеха с помощью кода без ответвлений. Вы вычисляете отдельные цифры и используете хэш-карту между значениями и цифрами. Вместо этого вы можете искать каждую цифру в массиве за постоянное время и объединять результаты для всех цифр.
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]
}
(Ранее я приводил гораздо худшую реализацию.) В этой версии для эффективности используются статические неизменяемые таблицы поиска фрагментов строк: компилятору не нужно выполнять какую-либо их инициализацию во время выполнения. Первый член конкатенации строк преобразуется .to_string()для получения временного String к которому можно добавить. Затем это возвращается с копированием elision. Функция должна выполнять приведение типа вверху, потому что индексы массива в Rust имеют тип usizeи язык не примет подписанный индекс.
Этот код примерно эквивалентен конкатенации значений из constexpr std::string_view[] таблицы на С++.
Существуют более быстрые решения, которые, например, перебирают обратные десятичные цифры ввода, а не выполняют модульную арифметику.