[玩rust
迭代器和lambda,我已经实现了N
质数生成器(original playground / improved code.)。与我在同一个盒子上精通的其他语言的等效功能代码相比,它的性能非常差(慢10倍)。一些数字:
test calc_primes ...基准:7,754,795 ns / iter(+/- 1,887,591)
#[macro_use]
extern crate bencher;
use bencher::Bencher;
use nth_prime::*;
fn calc_primes(b: &mut Bencher) {
b.iter(|| primes(10000));
}
benchmark_group!(benches, calc_primes);
benchmark_main!(benches);
我希望锈能胜过锈,但是我努力摆脱下面代码中的缺陷。因此,这是帮助优化此特定实现的呼吁。
Vec
分配,肯定不需要一些...OR
上使用逻辑bitarray
,这非常快。锈迹下面的逻辑在fold
调用中表达了相同的方法,但这使用的是Vec<bool>
,与位数组等效时,它必须很慢...Vec<bool>
,不介意分配大量的字节数组并进行移位等操作,但无法想象将其组合在一起...pub fn primes(n: u64) -> Vec<usize> {
if n < 4 {
vec![2]
} else {
base(primes((n as f64).sqrt().ceil() as u64), n)
}
}
fn base(r: Vec<usize>, p: u64) -> Vec<usize> {
let fvec = (0..p).map(|_| false).collect::<Vec<bool>>();
let z = r
.iter()
.map(|&x| (0..x).map(|y| y > 0).collect::<Vec<bool>>())
.map(|x| {
(0..p)
.map(|n| !x[(n % (x.len() as u64)) as usize])
.collect::<Vec<bool>>()
})
.fold(fvec, |acc, x| {
acc.iter().zip(x).map(|(a, b)| *a || b).collect()
});
let yy: Vec<usize> = z
.iter()
.enumerate()
.filter_map(|(i, x)| if !*x { Some(i) } else { None })
.skip(1)
.collect();
r.iter().chain(yy.iter()).map(|x| *x).collect()
}
关于素数生成算法,在this thread中有一个出色的答案,因此这不是关于优化算法的问题,而是这种没有外部包装的特定实现(这是一项学习练习)。
编辑:
经过评论部分的一些提示后,对其进行了显着优化:
test calc_primes ... bench: 4,776,400 ns/iter (+/- 1,427,534)
test calc_primes_sieve ... bench: 644,220 ns/iter (+/- 1,655,581)
test calc_primes_2 ... bench: 268,598 ns/iter (+/- 46,440)
Vec<bool>
@ fold
位图:step_by
fn base2(head: Vec<u64>, p: u64) -> Vec<u64> {
let mut fvec = (0..p).map(|_| false).collect::<Vec<bool>>();
head.iter()
.map(|&x| {
(0..p)
.step_by(x as usize)
.for_each(|y| fvec[y as usize] = true)
})
.for_each(drop);
let tail: Vec<u64> = fvec.iter().enumerate()
.filter_map(|(i, x)| if !*x { Some(i as u64) } else { None })
.skip(1)
.collect();
head.iter().chain(tail.iter()).cloned().collect()
}
编辑2:
供参考,这是“其他”语言的实现:
q)p:{$[x<4; enlist 2; r, 1_ where not any x#'not til each r:p ceiling sqrt x]} q)\ts do[1000;p 10000] 474 443088 = 474,000 ns/iter
对于翻译语言来说还不错。
编辑3
[从答案中为新实现添加了更多基准。(按时间顺序显示)
无需skip(1)
和diff fvec
分配即可删除tad位New playground code.test ssqrt_p_1__vec_bool_n_mod ... bench: 6,838,150 ns/iter (+/- 627,389) test sieve_p_2__mut_step_by ... bench: 367,229 ns/iter (+/- 38,279) test ssqrt_p_3__mut_step_by ... bench: 266,189 ns/iter (+/- 56,215) test ssqrt_p_4__push_step_by_mod ... bench: 1,255,206 ns/iter (+/- 262,107) test sieve_p_5__for_loop_mut ... bench: 441,397 ns/iter (+/- 47,077) test ssqrt_p_6__no_skip ... bench: 176,186 ns/iter (+/- 24,765)
StdDev现在起着重要的作用……运行:
任务集-c 0货板凳-工作1
fn base3(head: Vec<u64>, p: u64) -> Vec<u64> { let mut fvec = vec![false; p as usize]; fvec[1] = true; head.iter() .map(|&x| { (0..p) .step_by(x as usize) .for_each(|y| fvec[y as usize] = true) }) .for_each(drop); let tail: Vec<u64> = fvec .iter() .enumerate() .filter_map(|(i, x)| if !*x { Some(i as u64) } else { None }) .collect(); head.iter().chain(tail.iter()).cloned().collect() }
编辑5
令人惊讶的是,低于no_chain
比base3:no_skip
版本慢。猜猜是编译器magic
fn base4(head: Vec<u64>, p: u64) -> Vec<u64> {
let mut fvec = vec![false; p as usize]; fvec[1] = true;
head.iter()
.map(|&x| {
(0..p)
.step_by(x as usize)
.for_each(|y| fvec[y as usize] = true);
fvec[x as usize] = false;
})
.for_each(drop);
fvec.iter().enumerate()
.filter_map(|(i, x)| if !*x { Some(i as u64) } else { None })
.collect()
}
[使用锈迭代器和lambda,我已经实现了N个素数生成器(原始游乐场/改进的代码。)。与等效功能相比,它的性能非常差(慢10倍)...
您的代码有一些非常奇怪的开销,例如