如何组成可变的迭代器?

德亨里

编者注:此代码示例来自1.0之前的Rust版本,在语法上不是有效的Rust 1.0代码。此代码的更新版本会产生不同的错误,但是答案仍然包含有价值的信息。

我想做一个生成素数流的迭代器。我一般的想法是用迭代器包装一个迭代器,例如从

let mut n = (2..N)

然后,对于每个素数,对迭代器进行突变并添加一个过滤器

let p1 = n.next()
n = n.filter(|&x| x%p1 !=0) 
let p2 = n.next()
n = n.filter(|&x| x%p2 !=0) 

我正在尝试使用以下代码,但似乎无法正常工作

struct Primes {
    base: Iterator<Item = u64>,
}

impl<'a> Iterator for Primes<'a> {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let p = self.base.next();
        match p {
            Some(n) => {
                let prime = n.clone();
                let step = self.base.filter(move |&: &x| {x%prime!=0});
                self.base = &step as &Iterator<Item = u64>;
                Some(n)                
            },
            _ => None
        }        
    }
}

我对这种变化有所了解,但似乎无法获得寿命和类型相匹配的东西。现在编译器告诉我

  1. 我无法变异self.base
  2. 可变素数的寿命不足

这是我得到的错误

solution.rs:16:17: 16:26 error: cannot borrow immutable borrowed content `*self.base` as mutable
solution.rs:16         let p = self.base.next();
                                                     ^~~~~~~~~
solution.rs:20:28: 20:37 error: cannot borrow immutable borrowed content `*self.base` as mutable
solution.rs:20                 let step = self.base.filter(move |&: &x| {x%prime!=0});
                                                                ^~~~~~~~~
solution.rs:21:30: 21:34 error: `step` does not live long enough
solution.rs:21                 self.base = &step as &Iterator<Item = u64>;
                                                                  ^~~~
solution.rs:15:39: 26:6 note: reference must be valid for the lifetime 'a as defined on the block at 15:38...
solution.rs:15     fn next(&mut self) -> Option<u64> {
solution.rs:16         let p = self.base.next();
solution.rs:17         match p {
solution.rs:18             Some(n) => {
solution.rs:19                 let prime = n.clone();
solution.rs:20                 let step = self.base.filter(move |&: &x| {x%prime!=0});
                                     ...
solution.rs:20:71: 23:14 note: ...but borrowed value is only valid for the block suffix following statement 1 at 20:70
solution.rs:20                 let step = self.base.filter(move |&: &x| {x%prime!=0});
solution.rs:21                 self.base = &step as &Iterator<Item = u64>;
solution.rs:22                 Some(n)                
solution.rs:23             },
error: aborting due to 3 previous errors

为什么Rust不让我这样做?

弗拉基米尔·马特维耶夫(Vladimir Matveev)

这是一个工作版本:

struct Primes<'a> {
    base: Option<Box<Iterator<Item = u64> + 'a>>,
}

impl<'a> Iterator for Primes<'a> {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let p = self.base.as_mut().unwrap().next();
        p.map(|n| {
            let base = self.base.take();
            let step = base.unwrap().filter(move |x| x % n != 0);
            self.base = Some(Box::new(step));
            n
        })
    }
}

impl<'a> Primes<'a> {
    #[inline]
    pub fn new<I: Iterator<Item = u64> + 'a>(r: I) -> Primes<'a> {
        Primes {
            base: Some(Box::new(r)),
        }
    }
}

fn main() {
    for p in Primes::new(2..).take(32) {
        print!("{} ", p);
    }
    println!("");
}

我正在使用Box<Iterator>特征对象。装箱是不可避免的,因为内部迭代器必须存储在两次next()调用之间的某个位置,并且没有地方可以存储引用特征对象。

我将内部迭代器设为Option这是必要的,因为您需要用消耗它的值替换它,因此内部迭代器可能会在很短的时间内不存在于结构中。Rust用建模缺席OptionOption::take替换其调用的值,None并返回其中的所有在对不可复制的对象进行随机排列时,这很有用。

但是请注意,此筛分实现将同时导致内存不足和计算效率低下-对于每个素数,您都将创建一个额外的迭代器层,该迭代器将占用堆空间。另外,调用时堆栈的深度next()会随着素数的增加而线性增加,因此,如果有足够大的数目,则会导致堆栈溢出:

fn main() {
    println!("{}", Primes::new(2..).nth(10000).unwrap());
}

运行它:

% ./test1 

thread '<main>' has overflowed its stack
zsh: illegal hardware instruction (core dumped)  ./test1

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章