2
\$\begingroup\$

I'm learning Rust by completing a variety of coding challenges, such as the Google Codejam problem stated in the title. I completed a Python 3 implementation that I liked, which I then tried to port over to Rust.

To my surprise, the Python implementation appeared to be considerably faster: when I ran time python3 ../a.py ../A-large-practice.in > /dev/null, I got times of roughly .075s for each Python run as compared to when I ran time cargo run --release ../A-large-practice.in > /dev/null for which I got roughly .210s for each Rust run. These times come from averaging the sums of the usr and sys outputs generated by running the time command around 10 times per language.

How can I improve my Rust implementation so that it better conforms to best practices and also ends up being faster (at least to a level comparable with the Python implementation)?

use std::env::args;
use std::fs::File;
use std::io::Read;

fn main() {
    let args: Vec<String> = args().collect();
    let mut input = String::new();
    let mut f = File::open(&args[1]).unwrap();
    f.read_to_string(&mut input).unwrap();

    let mut input = input.lines();
    let num_inputs: u32 = match input.next() {
        None => panic!("No contents."),
        Some(num) => {
            match num.trim().parse() {
                Ok(num) => num,
                Err(_) => panic!("First line in input not a number."),
            }
        }
    };

    for i in 0..num_inputs {
        let mut score = 0;
        let moods: Vec<char> = match input.next() {
            None => panic!("Missing content."),
            Some(mood) => mood.chars().collect(),
        };
        let mut problems: Vec<&char> = Vec::new();
        for (j, mood) in moods.iter().enumerate() {
            /*
             * the assumption is that you'll only request problems that're the same mood that the grader is in
             * reason being that you can receive a maximum of 10 points and a minimum of 5,
             * whereas for the other mood it'll be a max of 5 and a min of 0
             */
            if problems.is_empty() {
                problems.push(mood);
            } else if problems.len() >= moods.len() - j {
                if problems.last() == Some(&mood) {
                    score += 10;
                } else {
                    score += 5;
                }
                problems.pop();
            } else if problems.last() == Some(&mood) {
                score += 10;
                problems.pop();
            } else {
                problems.push(mood);
            }
        }
        println!("Case #{}: {}", i+1, score);
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Note that the code I have below runs at about 3x the speed of the Python times you have listed (22ms vs 75ms) and almost 10x the speed of the Rust code. There's no large algorithmic differences between my Rust code and this code, so I feel that something still differs between the two methodologies. \$\endgroup\$
    – Shepmaster
    Jul 27 '16 at 18:18
2
\$\begingroup\$
  1. There's no need to collect all the arguments into a vector to ignore all but one. Just grab that one via nth.
  2. Remove most of the explicit types and prefer inferring them instead.
  3. Use expect instead of unwrap to provide a message when it fails. It took me 10 minutes to realize that the first argument had to be a filename and not the number of lines to read from standard input.
  4. It's shorter to use expect instead of a panic! when you can.
  5. Don't provide full type for collect; let the inner type be inferred with Vec<_>.
  6. Use the iterator in the for loop instead of calling next manually.
  7. Extract functions to give structure, add names, and isolate mutability.

use std::env::args;
use std::fs::File;
use std::io::Read;

fn read_input_file(name: &str) -> String {
    let mut input = String::new();
    let mut f = File::open(&name).expect("Unable to open the input file");
    f.read_to_string(&mut input).expect("Unable to read the input file");
    input
}

fn main() {
    let filename = args().nth(1).expect("Provide an input file as an argument");

    let input = read_input_file(&filename);
    let mut input = input.lines();

    let num_inputs = input.next().expect("No contents");
    let num_inputs = num_inputs.trim().parse().expect("First line in input not a number");

    for (i, line) in input.take(num_inputs).enumerate() {
        let mut score = 0;
        let moods: Vec<_> = line.chars().collect();
        let mut problems = Vec::new();

        for (j, &mood) in moods.iter().enumerate() {
            // the assumption is that you'll only request problems
            // that're the same mood that the grader is in reason
            // being that you can receive a maximum of 10 points and a
            // minimum of 5, whereas for the other mood it'll be a max
            // of 5 and a min of 0

            if problems.is_empty() {
                problems.push(mood);
            } else if problems.len() >= moods.len() - j {
                if problems.last() == Some(&mood) {
                    score += 10;
                } else {
                    score += 5;
                }
                problems.pop();
            } else if problems.last() == Some(&mood) {
                score += 10;
                problems.pop();
            } else {
                problems.push(mood);
            }
        }
        println!("Case #{}: {}", i+1, score);
    }
}

When profiling, it is very important to compile in release mode. You will also want to make sure you aren't including compilation time. I tend to split the compile and execute steps into two parts to be sure nothing extra is included:

$ cargo build --release
$ time ./target/release/gc3 A-large-practice.in

# ...snipped output...

real    0m0.022s
user    0m0.010s
sys     0m0.010s
\$\endgroup\$
5
  • \$\begingroup\$ I'm still going through the comments you made about the code, but your recommendation to split the build part out of timing the run has reduced the time to basically how long it takes to print to the file / to the screen - i.e. user and sys are 0, with real being a very marginally small amount. \$\endgroup\$
    – Amndeep7
    Jul 27 '16 at 18:23
  • \$\begingroup\$ Why is this the case? My understanding was that if the code hadn't been touched, then cargo run would basically just act as a wrapper to call the executable. \$\endgroup\$
    – Amndeep7
    Jul 27 '16 at 18:24
  • 1
    \$\begingroup\$ @Amndeep7 if the code hadn't been touched — figuring out if something has changed takes time itself. \$\endgroup\$
    – Shepmaster
    Jul 27 '16 at 18:38
  • \$\begingroup\$ That makes sense - I guess it's doing a bit more than just a stat on all the files and comparing it to whatever metadata it has on hand. \$\endgroup\$
    – Amndeep7
    Jul 27 '16 at 18:42
  • \$\begingroup\$ @Amndeep7 yup, it's got quite a bit more than just timestamp checking :-) \$\endgroup\$
    – Shepmaster
    Jul 27 '16 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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