2
\$\begingroup\$

I am trying to move from Python to a systems programming language so this is a bit of a challenge for me.

fn main() {
    let mut total_pow = 0;
    for x in 2..360000 { 
        let values: Vec<char> = x.to_string().chars().collect();
        let mut total = 0;
        for i in values {
            let value = i.to_digit(10).unwrap();
            total += value.pow(5);
        }
        if total == x {
            total_pow += x
        }
    }
    println!("Numbers {}", total_pow);
}

It runs in just under 1 second, which I think is slow:

$ time cargo run
Total: 443839
real  0m0.894s
user  0m0.888s
sys   0m0.012s

After building with the --release flag the time has greatly improved:

$ time cargo run --release
Numbers 443839

real  0m0.083s
user  0m0.072s
sys   0m0.012s

Some of my concerns are:

  1. Converting x, the loop value, to a char array and then converting each char back into a digit to perform pow on. Is there an easier way? In Python it is really simple (list(str(x))).

  2. I feel the speed of this is really slow.

  3. Best practices for rust/systems level code. I realize this is a fairly simple program but I want to make sure that I learn the good habits early.

\$\endgroup\$
2
\$\begingroup\$

If you want to measure the execution time of your program, run it directly, rather than going through Cargo, which adds some overhead of its own.

$ time cargo run --release
     Running `target/release/pe30`
Numbers 443839

real    0m0.111s
user    0m0.087s
sys     0m0.027s

$ time ./target/release/pe30 
Numbers 443839

real    0m0.045s
user    0m0.040s
sys     0m0.003s

(Cargo's overhead was much worse in the 0.2.0 nightly I first tried this with...)

The Rust compiler generates quite suboptimal code in debug builds, so don't worry too much about it.

Now for the code review proper:

let values: Vec<char> = x.to_string().chars().collect();

There is no need to collect() if all you're going to do is iterate on the collection. chars() returns a struct that implements Iterator, so you can use directly in a for loop.

let values = x.to_string().chars();

Oops, that doesn't compile:

src/main.rs:4:22: 4:35 error: borrowed value does not live long enough
src/main.rs:4         let values = x.to_string().chars();
                                   ^~~~~~~~~~~~~

We need to keep the value of x.to_string() alive, since the value of x.to_string().chars() refers to it. (You can discover that from the fact that Chars has a lifetime parameter ('a).) Let's split up the expression:

let x_str = x.to_string();
let values = x_str.chars();

But rather than using the builtin to_string(), we can generate the digits of a number arithmetically:

fn digits(mut n: u32) -> Vec<u32> {
    if n == 0 {
        vec![0]
    } else {
        let mut digits = Vec::new();
        while n > 0 {
            digits.push(n % 10);
            n /= 10;
        }

        digits
    }
}

fn main() {
    let mut total_pow = 0;
    for x in 2..360000 {
        let digits = digits(x);
        let mut total = 0;
        for digit in digits {
            total += digit.pow(5);
        }
        if total == x {
            total_pow += x
        }
    }
    println!("Numbers {}", total_pow);
}

(digits produces the digits from least-significant to most-significant; the order isn't important in this algorithm.)


At this point, I think the code is pretty optimal. However, Rust also encourages functional-style programming. Why not take a look?

First, let's change this loop:

let mut total = 0;
for digit in digits {
    total += digit.pow(5);
}

into a fold:

let total = digits.iter().fold(0, |sum, digit| sum + digit.pow(5));

fold lets you produce a single value from an Iterator. You specify the initial value, then a function to call on each item that returns the accumulator to pass to the next item, or to return if the end is reached. When you compile with --release, fold is often inlined.

We can do the same again with the outer loop:

let total_pow = (2..360000).fold(0, |total_pow, x| {
    let digits = digits(x);
    let total = digits.iter().fold(0, |sum, digit| sum + digit.pow(5));
    if total == x {
        total_pow + x
    } else {
        total_pow
    }
});

This big closure looks a bit messy, though. Let's break up the problem further. First, we want to obtain the list of numbers that can be written as the sum of fifth powers of their digits. Then, we want to sum that list.

For the first task, we need to eliminate numbers that don't apply. To keep only some items from a list, we can use filter. filter returns a new Iterator, on which we can apply fold to get the sum.

fn main() {
    let total_pow = (2..360000).filter(|&x| {
        x == digits(x).iter().fold(0, |sum, digit| sum + digit.pow(5))
    }).fold(0, |total_pow, x| {
        total_pow + x
    });
    println!("Numbers {}", total_pow);
}

If you're using a nightly compiler, you can also use sum (unstable at the time of writing). For the outer fold, we can use sum directly. For the inner fold, we could first use map to turn the sequence of digits into a sequence of their fifth powers, then sum them up. (I had to add a type annotation on total_pow, for some reason.)

#![feature(iter_arith)] // for Iterator::sum()

fn digits(mut n: u32) -> Vec<u32> {
    if n == 0 {
        vec![0]
    } else {
        let mut digits = Vec::new();
        while n > 0 {
            digits.push(n % 10);
            n /= 10;
        }

        digits
    }
}

fn main() {
    let total_pow: u32 = (2..360000).filter(|&x| {
        x == digits(x).iter().map(|digit| digit.pow(5)).sum()
    }).sum();
    println!("Numbers {}", total_pow);
}

Functional style can make program quite shorter, but also somewhat hard to read when you're not used to it. I encourage you to get used to it, because you're likely to encounter this style again when reading other people's Rust code.

\$\endgroup\$
  • \$\begingroup\$ The functional style is so much better in my opinion. I am glad you added that to your solution. I am interested in learning more about functional programming in rust and I think this is a great start. Thanks \$\endgroup\$ – Jared Mackey Oct 5 '15 at 16:17
2
\$\begingroup\$

Building on Francis Gagné's answer, I see that it takes 40ms. So I did some profiling:

Running Time    Self        Symbol Name
38.2ms   99.9%  6.9     e30::main
24.5ms   64.1%  1.1     |- e30::raw_vec::RawVec<T>::double
 5.2ms   13.6%  0.1     |- e30::heap::deallocate

You can see that the majority of the time is spent in allocating and reallocating memory for the number vector. We know that a 32-bit unsigned integer has a maximum of 10 digits, so lets preallocate the vector to that size. I also reordered the digit function to not have a special case for zero:

// Allocate the right amount just once
fn digits(mut n: u32) -> Vec<u32> {
    let mut digits = Vec::with_capacity(10);

    loop {
        digits.push(n % 10);
        n /= 10;

        if n == 0 { break }
    }

    digits
}

We are now down to 21ms. Let's profile again:

Running Time    Self        Symbol Name
14.4ms  100.0%  6.4     e30::main
 4.6ms   31.9%  0.0     |- e30::heap::deallocate
 2.8ms   19.4%  2.4     |- je_mallocx

Now it's just heap allocation at all. Let's return a stack-allocated array:

// No heap allocation
fn digits(mut n: u32) -> [u32; 10] {
    let mut digits = [0; 10];
    let mut i = 0;

    loop {
        digits[i] = n % 10;
        n /= 10;

        if n == 0 { break }
        i += 1;
    }

    digits
}

Now we are down to 12ms, which is pretty close to the C version that user5402 posted. However, having to treat the array like that is kind of ugly. In real code, I'd probably look to use the arrayvec library to abstract that a bit:

extern crate arrayvec;
use arrayvec::ArrayVec;

// No heap allocation
fn digits(mut n: u32) -> ArrayVec<[u32; 10]> {
    let mut digits = ArrayVec::<[_; 10]>::new();

    loop {
        digits.push(n % 10);
        n /= 10;

        if n == 0 { break }
    }

    digits
}

Unfortunately, this bumps the time back up a bit to 16ms. Not sure why, perhaps there's some optimization that can be done in that library. It's up to you to decide how important that last bit of performance really is!

\$\endgroup\$
0
\$\begingroup\$

Some of my concerns are:

  1. Converting x, the loop value, to a char array and then converting each > char back into a digit to perform pow on. Is there an easier way? In Python it is really simple (list(str(x))).

  2. I feel the speed of this is really slow.

If you want to avoid the number <-> string conversion all the time, and you want speed, just keep track of the individual digits in an array.

Here is a C program to demonstrate how it would work - I'm sure the Rust version would look almost the same.

#include <stdio.h>

int digit[6] = { 0 };
int sum5[7] = { 0 };
int d5[10];

int main() {
  for (int d = 0; d < 10; ++d) {
    d5[d] = d*d*d*d*d;
  }

  int answer = 0;

  digit[0] = 1;
  sum5[0] = 1;
  for (int n = 2; n <= 360000; ++n) {
    // increment digits
    int k = 0;
    while (1) {
      digit[k]++;
      if (digit[k] <= 9)
        break;
      digit[k] = 0;
      k++;
    }
    // adjust sum5[]
    while (k >= 0) {
      sum5[k] = sum5[k+1] + d5[ digit[k] ];
      k--;
    }
    if (sum5[0] == n) {
      answer += n;
    }
  }
  printf("%d\n", answer);
}

This runs in 0.011 secs on my ancient Core2Duo.

\$\endgroup\$

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.