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

Question

我已经开始研究 Rust 和 came across #3 where the easiest quick-approach would be to implement a Sieve of Eratosthenes 中的 Project Euler 问题。

在这样做时，我的算法创建了一个迭代器，然后从中过滤出非素数并将其分配回原始向量，但我收到一个错误，指出 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
}

错误：

error[E0277]: a collection of type `std::vec::Vec<u32>` cannot be built from an iterator over elements of type `&u32`
  --> src\main.rs:42:55
   |
42 |         range = range.iter().filter(|&n| *n % p != 0).collect();
   |                                                       ^^^^^^^ a collection of type `std::vec::Vec<u32>` cannot be built from `std::iter::Iterator<Item=&u32>`
   |
   = help: the trait `std::iter::FromIterator<&u32>` is not implemented for `std::vec::Vec<u32>`

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

Answer 1

说明

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

迭代器链的filter(...)部分实际上与你的问题无关。当我们看一下Iterator::filter, we see that it returns 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 returns slice::Iter<T> 实现 Iterator:

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

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

解决方案

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

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

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

另请注意，我删除了 *n 中的 *，因为不再需要解除引用。

其他提示

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

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

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

Unable to collect a filtered a Vec into itself

filter

prime-factoring

rust

说明

解决方案

其他提示