编者注:这个问题使用了在Rust 1.0之前删除的一些函数和类型。这些想法仍然有效,但代码不能在Rust 1.0中运行。
我试图通过实现Eratosthenes Sieve作为迭代器来解决使用Rust的Project Euler问题#3。
在经历了一些大脑爆炸尝试后,我停止了here。
use std::iter::count;
struct EratosthenesStream<'a> {
sieve: &'a (Iterator + 'a),
}
impl<'a> EratosthenesStream<'a> {
fn new() -> EratosthenesStream<'a> {
EratosthenesStream {
sieve: &count(2, 1),
}
}
}
impl<'a> Iterator for EratosthenesStream<'a> {
type Item = isize;
fn next(&mut self) -> Option<isize> {
let prime = self.sieve.next().expect("Out of numbers");
self.sieve = self.sieve.filter(|&x| x % prime == 0);
Some(prime)
}
}
fn main() {
// let sieve = EratosthenesStream::new();
// for i in sieve.take(5) {
// println!("{}", i);
// }
}
建造那件东西给了我:
Compiling problem3 v0.0.1 (file:///home/franza/Projects/euler-project-rust/problem3)
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:16:33: 16:45 error: the value of the associated type `Item` (from the trait `core::iter::Iterator`) must be specified
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:16 EratosthenesStream { sieve: &count(2, 1) }
^~~~~~~~~~~~
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25:29: 25:56 error: type `&'a core::iter::Iterator + 'a` does not implement any method in scope named `filter`
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25 self.sieve = self.sieve.filter(|&x| x % prime == 0);
^~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25:41: 25:42 error: the type of this value must be known in this context
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25 self.sieve = self.sieve.filter(|&x| x % prime == 0);
^
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25:36: 25:55 error: can't infer the "kind" of the closure, explicitly annotate it. e.g. `|&:| {}`
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:25 self.sieve = self.sieve.filter(|&x| x % prime == 0);
^~~~~~~~~~~~~~~~~~~
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:26:5: 26:16 error: mismatched types: expected `core::option::Option<isize>`, found `core::option::Option<<core::iter::Iterator as core::iter::Iterator>::Item>` (expected isize, found associated type)
/home/franza/Projects/euler-project-rust/problem3/src/main.rs:26 Some(prime)
^~~~~~~~~~~
error: aborting due to 5 previous errors
Could not compile `problem3`.
我刚开始生锈,所以我对此并不了解
更新:
rustc 1.0.0-nightly (44a287e6e 2015-01-08 17:03:40 -0800)
cargo 0.0.1-pre-nightly (8c01b6b 2015-01-08 20:52:43 +0000)
编者注:这个答案使用了在Rust 1.0之前删除的一些函数和类型。这些想法仍然有效,但代码不能在Rust 1.0中运行。从那时起,一些错误也得到了修复。
这是计算素数的一种有趣的方法,但我不确定它现在可以与Rust一起使用。有很多错误,我们正在使用特征对象来制作它们......不是很好。
不过,我可以解决一些问题。
您正试图在结构中存储对迭代器的共享引用。这不会有两个原因:迭代器需要next
的可变性,并且迭代器不会活得足够长。
据推测,你需要在你的结构中使用像Box<Iterator + 'static>
这样的东西,但是由于上面提到的错误,这不是没有特别好的理由。
现在我担心你必须保持你明确看到的素数列表。我建议像:
struct Foo {
odds: Counter<u32>,
primes: Vec<u32>,
}
并且使用显式for循环的更“程序化”方法:
(不确定在这里提供完整的解决方案是否完全合适,所以如果你不想要剧透,请不要提前阅读,我猜?)
struct Foo {
odds: Counter<u32>,
primes: Vec<u32>,
}
impl Foo {
fn new() -> Foo {
Foo {
odds: count(2, 1),
primes: Vec::new(),
}
}
}
impl Iterator for Foo {
type Item = u32;
fn next(&mut self) -> Option<u32> {
'main: for i in self.odds {
for &prime in self.primes.iter() {
if i % prime == 0 {
continue 'main;
}
}
self.primes.push(i);
return Some(i);
}
None
}
}
fn main() {
let foo = Foo::new();
for i in foo.take(10) {
println!("{}", i);
}
}
现在#21361已经关闭,您可以这样实现:
use std::{iter, mem};
struct Sieve {
iter: Box<Iterator<Item = u64> + 'static>,
}
impl Sieve {
fn new() -> Sieve {
Sieve {
iter: Box::new(2..),
}
}
}
impl Iterator for Sieve {
type Item = u64;
fn next(&mut self) -> Option<u64> {
let mut iter = mem::replace(&mut self.iter, Box::new(iter::empty()));
match iter.next() {
Some(prime) => {
self.iter = Box::new(iter.filter(move |x| x % prime != 0));
Some(prime)
}
None => None,
}
}
}
fn main() {
let v: Vec<_> = Sieve::new().take(20).collect();
println!("{:?}", v);
}
关于实施的一些注意事项:
x % prime != 0
。 ^ _ ^filter
consumes the iterator,但这会引起问题。如果我们被允许使用它,那么Sieve
结构将不再是完整且有效的。要解决这个问题,我们使用mem::replace
来放置占位符值。这让我们在使用新值更新结构之前使用迭代器。这个问题的关键是filter
迭代器而不移动它,这可以通过使用take_mut
来完成。
将take_mut = "0.2.2"
(或任何其他兼容版本)添加到您的依赖项,然后您可以执行以下操作:
extern crate take_mut;
struct Primes {
iter: Box<Iterator<Item=i64>>,
}
impl Iterator for Primes {
type Item=i64;
fn next(&mut self) -> Option<i64> {
let result = self.iter.next();
if let Some(prime) = result {
take_mut::take(&mut self.iter,
|primes| Box::new(primes.filter(move |p| p % prime != 0)));
}
result
}
}
impl Primes {
fn new() -> Primes {
Primes { iter: Box::new(2..)}
}
}
fn main() {
println!("First 10 primes:");
for p in Primes::new().take(10) {
println!("{}", p);
}
}
编辑:Option::take
也可以做这个工作。
struct Primes {
iter: Option<Box<Iterator<Item = u64>>>,
}
impl Primes {
fn new() -> Primes {
Primes {
iter: Some(Box::new(2..)),
}
}
}
impl Iterator for Primes {
type Item = u64;
fn next(&mut self) -> Option<u64> {
let mut iter = self.iter.take()?;
let result = iter.next();
if let Some(prime) = result {
self.iter = Some(Box::new(iter.filter(move |n| n % prime != 0)));
}
result
}
}