In Rust, is there a way to perform a retain() on only part of a container?

user_9217033 0
Viewed 1979

I'm learning Rust for fun, and when writing a function to return the nth prime, I realized my solution felt inelegant and wasteful.

I iterate through my entire list of possible primes, when I only want to iterate through the part of it that hasn't been verified. Is there a way to do this while using the retain() function?

My main issue is that I believe the retain() function is implemented for Vec, and not for a slice. I tried looking into slice documentation for further ideas, but couldn't find any.

Here is the code.

let mut prime_list: Vec<u32> = (2..n).collect();
let mut i: usize = 0;
while i < prime_list.len() {
    let prime: u32 = prime_list[i];
    prime_list.retain(
       |x| x <= &prime || x % &prime != 0);
    i += 1;
}

So the issue is in the function call

prime_list.retain(
    |x| x <= &prime || x % &prime != 0);

I don't need to go over every element in my list each time I pop into this loop since I know that I've verified the elements before 'i'.

But the retain() function needs to go over the entire container, so I add a check into it (x <= &prime || ...) to ignore all the elements before the current one.

What I'd like to do is elegantly start at element at position 'i', and go through the list removing elements.

I know I can do this with a less elegant while or for loop, but I'm hoping there is a Rust-way to do this elegantly.

Thanks for any help!

EDIT: here is a possible solution with splitting and filter() that feels more obfuscated than I think it should be... if there is a better way using the filter() method and iterators I'd really appreciate a nudge in the right direction.

// inside the while loop
let prime: u32 = prime_list[i];
let (left, right) = prime_list.split_at(i);

prime_list = left.iter()
    .chain(
         right.iter()
         .filter(|x| *x == &prime || *x % &prime != 0))
    .map(|&x| x)
    .collect();

i += 1;
rust primes vector
1 Answers

This doesn't solve exactly what you wanted, but I thought I'd give a shot at making a more "rust-way" of doing this as someone who has written rust for a little while.

let mut primes = Vec::new();

for e in 2..100 {
    if primes.iter().all(|p| e % p != 0) {
        primes.push(e);
    }
}

println!("{:?}", primes);

I store the primes in a separate vector because I want to add to it as I go along. This really feels a lot more elegant than trying to use retain to remove certain elements from a vector as you iterate over it.

If you really wanted to get fancy, you could optimize a bit by using with_capacity and stopping after you got your nth prime.

fn get_nth_prime(n: usize) -> u32 {
    let mut primes = Vec::with_capacity(n);
    let mut e = 2;

    while primes.len() < n {
        if primes.iter().all(|p| e % p != 0) {
            primes.push(e);
        }

        e += 1;
    }

    primes[n - 1]
}
user_33903760
Related