4
\$\begingroup\$

I am in the process of learning Rust and am still having some issues with borrowing and ownership. I find myself trying to borrow mutable references that are already borrowed as immutable references etc...

I noticed that when I try to iterate over the primes without owning them, I encounter issues trying to modify the composites hash map. I was able to get around this by calling to_owned on the vector. Is this the right way to handle this?

I also see that when I build the code, I get warnings about unused code for warning: struct is never constructed: 'Sieve' and warning: method is never used: 'new', am I constructing them incorrectly?

use std::collections::HashMap;

struct Sieve {
    composites: HashMap<u64, Vec<u64>>,
    x: u64,
}

impl Sieve {
    fn new() -> Sieve {
        Sieve {
            composites: HashMap::new(),
            x: 2,
        }
    }
}

impl Iterator for Sieve {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let x = self.x;
        self.x = self.x + 1;
        match self.composites.get(&x) {
            Some(numbers) => {
                for _num in numbers.to_owned() {
                    self.composites
                        .entry(x + _num)
                        .and_modify(|v| v.push(_num))
                        .or_insert(vec![_num]);
                }
                self.composites.remove(&x);
                self.next()
            }
            None => {
                self.composites.insert(x * x, vec![x]);
                Some(x)
            }
        }
    }
}

fn main() {
    let mut sieve = Sieve::new();

    println!("{:?}", sieve.next()); // 2
    println!("{:?}", sieve.next()); // 3
    println!("{:?}", sieve.next()); // 5
    println!("{:?}", sieve.next()); // 7
}

Here is the code on the Rust playground.

I previously posted a version of the Sieve of Eratosthenes using experimental Rust features, this made it difficult to get feedback on. I have refactored the code to use iterators

\$\endgroup\$
  • \$\begingroup\$ when I build the code, I get warnings about unused code — in what context? If it's the playground, choosing build compiles your code as a library, so your main method would not be called and thus your code would be unused. \$\endgroup\$ – Shepmaster Mar 19 at 17:13
3
\$\begingroup\$

Your code is totally fine and idiomatic, but I would change some minor points:

use std::collections::HashMap;

struct Sieve {
    composites: HashMap<u64, Vec<u64>>,
    current: u64,
}

impl Default for Sieve {
    fn default() -> Self {
        Sieve {
            composites: HashMap::new(),
            current: 2,
        }
    }
}

impl Sieve {
    pub fn new() -> Sieve {
        Default::default()
    }
}

impl Iterator for Sieve {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        fn next_prime(composites: &mut HashMap<u64, Vec<u64>>, x: u64) -> u64 {
            match composites.get(&x) {
                Some(numbers) => {
                    for num in numbers.to_owned() {
                        composites
                            .entry(x + num)
                            .and_modify(|v| v.push(num))
                            .or_insert_with(|| vec![num]);
                    }
                    composites.remove(&x);
                    next_prime(composites, x + 1)
                }
                None => {
                    composites.insert(x * x, vec![x]);
                    x
                }
            }
        }

        let prime = next_prime(&mut self.composites, self.current);
        self.current = prime + 1; // This number will be the next to be tested

        Some(prime)
    }
}

fn main() {
    let mut sieve = Sieve::new();

    assert_eq!(sieve.next(), Some(2));
    assert_eq!(sieve.next(), Some(3));
    assert_eq!(sieve.next(), Some(5));
    assert_eq!(sieve.next(), Some(7));
}
  • It is good to implement Default when you can build your data structure without parameters (related answer).
  • This is a good practice to put assertions instead of prints. That's easier to change to code and verify that it is still ok.
  • The naming of the variables is important; but I do not pretend that mine is perfect, though. By the way, _num should not be prefixed with an underscore because it is used.
  • You can run clippy to catch some common error. Clippy warns you that you create a vec![_num] at each iteration. You should give to or_insert_with a closure that will build the correct vector.
  • The more important refactoring that I did is to make the algorithm more "functional". I think that yours is difficult to reason about because it calls recursively the Iterator::next method and rely on internal state.
\$\endgroup\$
  • \$\begingroup\$ Thank you for the feedback, I really appreciate it. Clippy looks great btw. I like your idea of not actually calling the next method recursively and offloading it to another function. Is there any performance benefit to moving the next_prime def outside of the next method? \$\endgroup\$ – kyle Mar 20 at 13:11
  • 2
    \$\begingroup\$ That's mainly a readability difference (separate the pure calculation from the iterator implementation). I think that the performance would be the same, but if you want to be sure, you must benchmark this. \$\endgroup\$ – French Boiethios Mar 20 at 13:43
3
\$\begingroup\$

I have some more suggestions that can improve your code.

  • You can avoid cloning numbers by just removing it from composites to begin with, since you already remove it later. HashMap::remove will give you an Option<Vec<u64>>, so you can now modify the hashmap while you iterate over the vec because it is no longer owned by the hashmap.
  • You can make your function iterative by using a while let loop.
  • You can simplify your usage of entry by just using or_default which will give a mutable reference to either the vec that was already there, or an empty one. Then you can just push into that vec.
  • Another option for clarity is to make a next_prime method on Sieve.
impl Sieve {
    pub fn next_prime(&mut self) -> u64 {
        while let Some(numbers) = self.composites.remove(&self.current) {
            for num in numbers {
                self.composites
                    .entry(self.current + num)
                    .or_default()
                    .push(num)
            }
            self.current += 1;
        }
        let prime = self.current;
        self.composites.insert(prime * prime, vec![prime]);
        self.current += 1;
        prime
    }
}

impl Iterator for Sieve {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        Some(self.next_prime())
    }
}
\$\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.