Speedup counter game

Question

Я пытаюсь решить вопрос алгоритма Rust на hackerrank. Мой ответ истекает на некоторых более крупных тестах. Есть около 5 человек, которые завершили его, поэтому я считаю, что это возможно, и я предполагаю, что они скомпилируются в режиме выпуска. Есть ли ускорения, которых я не хватает?

Суть игры - счетчик (inp in main) условно снижен и основан на том, кто больше не может его уменьшить, выбирается победитель.

use std::io; 

fn main() { 
    let n: usize = read_one_line(). 
     trim().parse().unwrap(); 
    for _i in 0..n{ 
     let inp: u64 = read_one_line(). 
      trim().parse().unwrap(); 
     println!("{:?}", find_winner(inp)); 
    } 
    return; 
} 

fn find_winner(mut n: u64) -> String{ 
    let mut win = 0; 
    while n>1{ 
     if n.is_power_of_two(){ 
      n /= 2; 
     } 
     else{ 
      n -= n.next_power_of_two()/2; 
     } 
     win += 1; 
    } 
    let winner = 
     if win % 2 == 0{ 
      String::from("Richard") 
     } else{ 
      String::from("Louise") 
     }; 
    winner 
} 

fn read_one_line() -> String{ 
    let mut input = String::new(); 
    io::stdin().read_line(&mut input).expect("Failed to read"); 
    input 
} 

Answer 1

Ваш внутренний цикл может быть заменен комбинацией встроенных функций:

let win = if n > 0 { 
    n.count_ones() + n.trailing_zeros() - 1 
} else { 
    0 
}; 

Кроме того, вместо того, чтобы выделить строку каждый раз, когда find_winner называется, ломтик строка может быть возвращена:

fn find_winner(n: u64) -> &'static str { 
    let win = if n > 0 { 
     n.count_ones() + n.trailing_zeros() - 1 
    } else { 
     0 
    }; 

    if win % 2 == 0 { 
     "Richard" 
    } else{ 
     "Louise" 
    } 
} 

Answer 2

Избегание распределения памяти может помочь ускорить применение.

В данный момент функция read_one_line делает одно распределение памяти на вызов, который можно было бы избежать, если поставить String как &mut параметра:

fn read_one_line(input: &mut String) -> &str { 
    io::stdin().read_line(input).expect("Failed to read"); 
    input 
} 

Обратите внимание, как я также изменить тип возврата для возврата срез (который занимает input): в дальнейшем здесь не требуется изменять исходную строку.

---

Еще одним преимуществом является ввод-вывод. Ржавчина - все об эксплицитности, и это означает, что io::stdin() является сырым вводом/выводом: каждый вызов read_line вызывает взаимодействие с ядром.

Вы можете использовать (и должны) вместо буферизованного ввода-вывода с std::io::BufReader. Построить его один раз, а затем передать его в качестве аргумента:

fn read_one_line<'a, R>(reader: &mut R, input: &'a mut String) -> &'a str 
    where R: io::BufRead 
{ 
    reader.read_line(input).expect("Failed to read"); 
    input 
} 

Примечание:

• это легче сделать это родовое (R), чем указать точный тип BufReader :)
• аннотирования Срок службы является обязательным, так как тип возврата может занять либо параметр

---

Собирая вообще:

fn read_one_line<'a, R>(reader: &mut R, input: &'a mut String) -> &'a str 
    where R: io::BufRead 
{ 
    reader.read_line(input).expect("Failed to read"); 
    input 
} 

fn main() { 
    let mut reader = io::BufReader::new(io::stdin()); 
    let mut input = String::new(); 

    let n: usize = read_one_line(&mut reader, &mut input). 
     trim().parse().unwrap(); 

    for _i in 0..n{ 
     let inp: u64 = read_one_line(&mut reader, &mut input). 
      trim().parse().unwrap(); 
     println!("{:?}", find_winner(inp)); 
    } 
    return; 
} 

с большим выигрышем, вероятно, будучи I/O (может быть даже само по себе недостаточно).

Не забудьте также применить советы @ Джона, таким образом вы будете свободны от распределения в своей основной петле!