代码之家 › 专栏 › 技术社区 › Maximilian Burszley

无法将已筛选的向量收集到自身中

prime-factoring rust filter

2

Maximilian Burszley · 技术社区 · 6 年前

这个问题已经有了答案:

is it possible to filter on a vector in-place? 2答

我已经开始研究项目euler在rust和 came across #3 最简单的快速方法是 Sieve of Eratosthenes .

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

为什么闭包将值包装成额外的借出?

1 回复 | 直到 6 年前

1

2

Lukas Kalbertodt 6 年前

解释

根据错误消息,表达式 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> 哪些工具 迭代器 :

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 ,因为不再需要解引用。

其他提示

总是重新分配一个新向量不是很快。埃拉托舍内斯的筛子是以不同的方式实现的:不存储数字,只存储布尔值来表示每个数字是否是素数。这些数字从不显式存储,而是通过使用向量/数组的索引隐式存储。

为了让它更快,我们不应该使用 Vec<bool> 而是一个专用的bitvec。 vec<bool> 每存储一个字节 bool ,尽管只需要一个位。提供这种位向量的事实板条箱是 bit-vec ,这也方便地展示了一个Eratosthenes筛的示例实现 in its documentation .