无法将过滤后的 Vec 收集到自身中

Question

我已经开始解决 Rust 中的 Project Euler 问题，并遇到了#3，其中最简单的快速方法是实现埃拉托色尼筛法。

在此过程中，我的算法创建了一个迭代器，然后过滤掉非素数并将其分配回原始向量，但我收到了Vec<u32>无法从 构建的错误Iterator<Item=&u32>。

---

代码：

fn eratosthenes_sieve(limit: u32) -> Vec<u32> {
    let mut primes: Vec<u32> = Vec::new();
    let mut range: Vec<u32> = (2..=limit).collect();
    let mut length = range.len();

    loop {
        let p = range[0];
        primes.push(p);

        range = range.iter().filter(|&n| *n % p != 0).collect();

        if length == range.len() {
            break;
        }
        length = range.len();
    }

    primes
}

错误：

fn eratosthenes_sieve(limit: u32) -> Vec<u32> {
    let mut primes: Vec<u32> = Vec::new();
    let mut range: Vec<u32> = (2..=limit).collect();
    let mut length = range.len();

    loop {
        let p = range[0];
        primes.push(p);

        range = range.iter().filter(|&n| *n % p != 0).collect();

        if length == range.len() {
            break;
        }
        length = range.len();
    }

    primes
}

---

为什么闭包将这些值包装在额外的借用中？

Answer 1

解释

根据错误消息，该表达式range.iter().filter(|&n| *n % p != 0)是类型为 的项的迭代器&u32：对u32. u32您期望按值迭代器。那么让我们向后走：

迭代器链的部分filter(...)实际上与您的问题无关。当我们查看时Iterator::filter，我们看到它返回了Filter<Self, P>。该类型实现Iterator：

impl<I: Iterator, P> Iterator for Filter<I, P>
where
    P: FnMut(&I::Item) -> bool,
{
    type Item = I::Item;
    // ...
}

这里重要的部分是type Item = I::Item，这意味着（原始迭代器）的项目类型I被准确地传递。没有添加参考。

这剩下.iter()：这就是问题的原因。Vec::iter返回slice::Iter<T>实现Iterator：

impl<I: Iterator, P> Iterator for Filter<I, P>
where
    P: FnMut(&I::Item) -> bool,
{
    type Item = I::Item;
    // ...
}

T在这里我们看到项目类型是对（向量的元素类型）的引用。

解决方案

在一般情况下，您可以调用.cloned()任何迭代器来迭代引用，以获得一个新的迭代器，该迭代器按值迭代项目（通过克隆每个项目）。对于实现的类型，Copy您可以（并且应该）使用.copied(). 例如range.iter().filter(|&n| *n % p != 0).copied().collect()。

然而，在这种情况下，有一个更好的解决方案：因为之后不再需要向量，所以您可以调用into_iter()而iter()不是直接按值获取迭代器u32。这会消耗该向量，使其随后无法访问。但是，正如所说的，这在这里不是问题。

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    // ...
}

另请注意，我删除了*in *n，因为不再需要取消引用。

其他提示

总是重新分配一个新的向量并不是很快。埃拉托斯特尼筛法通常以一种不同的方式实现：不存储数字，而是只存储布尔值来表示每个数字是否是素数。这些数字永远不会显式存储，而是通过使用向量/数组的索引隐式存储。

为了使其变得非常快，不应该使用 a Vec<bool>，而应该使用专用的 bitvec。Vec<bool>每个存储一个字节bool，尽管只需要一位。提供这种位向量的事实上的箱子是，它还在其文档中bit-vec方便地显示了埃拉托斯特尼筛法的示例实现。