我想使用一些不错的旧Collatz conjecture并决定以(非常)函数样式进行操作会很有趣，因此我实现了一个unfoldr函数，与一个Haskell has接近:
fn unfoldr<F, T>(foo: F, seed: T, mut vec: Vec<T>) -> Vec<T>
where F: Fn(T) -> Option<(T, T)>
{
if let Some((x, y)) = foo(seed) {
vec.push(x);
unfoldr(foo, y, vec)
} else {
vec
}
}
其余的非常简单:
fn collatz_next(n: u64) -> u64 {
if n % 2 == 0 { n / 2 } else { 3 * n + 1 }
}
pub fn collatz_seq_f(n: u64) -> Vec<u64> {
unfoldr(|n| if n == 1 { None } else { Some((n, collatz_next(n))) }, n, Vec::new())
}
使用
collatz_seq_f返回一个Vec tor，其序列以给定数字n开头。但是，我想知道Rust是否批准这种样式，并实现了一个简单的命令式对应项:
pub fn collatz_seq_i(n: u64, mut vec: Vec<u64>) -> Vec<u64> {
let mut c = n;
while c != 1 {
vec.push(c);
c = collatz_next(c);
}
vec
}
并将它们与
cargo bench(0.13.0-nightly(2ef3cde 2016-09-04))进行比较。我感到很失望的是，我有趣的unfoldr方法的速度仅为命令执行速度的一半:running 3 tests
test tests::it_works ... ignored
test tests::bench_collatz_functional ... bench: 900 ns/iter (+/- 47)
test tests::bench_collatz_imperative ... bench: 455 ns/iter (+/- 29)
test result: ok. 0 passed; 0 failed; 1 ignored; 2 measured
我知道
unfoldr版本更抽象，但是我没想到会有太大的不同。有什么我可以改变以使其更快吗？完整代码如下:
#![feature(test)]
extern crate test;
fn unfoldr<F, T>(foo: F, seed: T, mut vec: Vec<T>) -> Vec<T>
where F: Fn(T) -> Option<(T, T)>
{
if let Some((x, y)) = foo(seed) {
vec.push(x);
unfoldr(foo, y, vec)
} else {
vec
}
}
fn collatz_next(n: u64) -> u64 {
if n % 2 == 0 { n / 2 } else { 3 * n + 1 }
}
pub fn collatz_seq_f(n: u64) -> Vec<u64> {
unfoldr(|n| if n == 1 { None } else { Some((n, collatz_next(n))) }, n, Vec::new())
}
pub fn collatz_seq_i(n: u64, mut vec: Vec<u64>) -> Vec<u64> {
let mut c = n;
while c != 1 {
vec.push(c);
c = collatz_next(c);
}
vec
}
#[cfg(test)]
mod tests {
use super::*;
use test::Bencher;
#[test]
fn it_works() {
assert_eq!(110, collatz_seq_f(27).len());
assert_eq!(110, collatz_seq_i(27, Vec::new()).len());
}
#[bench]
fn bench_collatz_functional(b: &mut Bencher) {
b.iter(|| collatz_seq_f(27));
}
#[bench]
fn bench_collatz_imperative(b: &mut Bencher) {
b.iter(|| collatz_seq_i(27, Vec::new()));
}
}
最佳答案
这将包含为什么unfoldr有点慢的一些实现细节。
我提出了一个不同的变体，@breeden帮助我验证了它的改进，使其与性能势在必行的变体相匹配。它确实保留了递归，但是我们不能再称它为功能了。[^ 1]
fn unfoldr2<F, T>(foo: F, seed: T, vec: &mut Vec<T>)
where F: Fn(T) -> Option<(T, T)>
{
if let Some((x, y)) = foo(seed) {
vec.push(x);
unfoldr2(foo, y, vec)
}
}
fn collatz_next(n: u64) -> u64 {
if n % 2 == 0 { n / 2 } else { 3 * n + 1 }
}
pub fn collatz_seq_f(n: u64) -> Vec<u64> {
let mut v = Vec::new();
unfoldr2(|n| if n == 1 { None } else { Some((n, collatz_next(n))) }, n, &mut v);
v
}
此处的区别将说明第一个版本的“错误之处”。在
unfoldr中，携带了vec值，而在unfoldr2中，仅存在对向量的可变引用。vec值在
unfoldr中起作用，并且您发现它限制了编译器:展开。如果某个函数出现紧急情况，那么放开就会发生。如果通过unfoldr函数展开，则必须删除所有局部变量，这意味着vec。插入一些特殊的代码来处理此问题(称为“着陆垫”)，并且可能会 panic 的函数调用会插入一条指令，以在发生 panic 时转移到着陆垫。因此在
unfoldr中:vec vec.push紧急情况)vec放下并恢复展开此外，还有一些代码可以移动Vec值。 (将其复制到堆栈中，以供登陆垫代码使用)。
unfoldr2并没有实现任何魔术般的递归到循环优化，但它的代码更少，因为它不需要处理展开或移动Vec。[^ 1]:我们是否可以通过将vec.push(x)想象为流/生成器/输出迭代器的接口(interface)，或者仅仅是回调来挽救功能性？