Rust中的Collat​​z猜想:功能性命令式方法

Question

我想玩一些旧的Collat​​z猜想并决定以(非常)功能的方式进行它很有趣,所以我实现了一个unfoldr函数,接近Haskell的一个:

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-夜间(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()));
    }
}

Answer 1

这不是一个答案,而是一个额外的测试,以缩小性能影响的来源.我Some通过编写递归函数展开了开销

pub fn collatz_seq_r(n: u64, mut vec: Vec<u64>) -> Vec<u64> {
    if n == 1 {
        vec
    } else {
        vec.push(n);
        collatz_seq_r(collatz_next(n), vec)
    } 
}

我获得了与collatz_seq_f示例几乎相同的性能.似乎LLVM没有展开此递归调用.

替代

在考虑如何在Rust中执行此操作后,我很可能已经实现了一个迭代器,其作用是使用函数连续组合先前的值,从而提供非终止的查询:n, f(n), f(f(n)), ..., f^k(n), ....这可以这样做:

struct Compose<T, F> {
    value: T,
    func: F
}

impl<T, F> Iterator for Compose<T, F> 
    where T: Copy,
          F: Fn(T) -> T {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        let res = self.value;                    // f^k(n)
        self.value = (self.func)(self.value);    // f^{k+1}(n)
        Some(res)
    }
}

impl<T, F> Compose<T, F> {
    fn new(seed: T, func: F) -> Compose<T, F> {
        Compose { 
            value: seed,
            func: func
        }
    }
}

所以在这里我可以调用Compose::new(seed_value, function)一个组合的迭代器.生成一个Collat​​z序列然后变成:

pub fn collatz_seq_iter(n: u64) -> Vec<u64> {
    Compose::new(n, collatz_next)
             .take_while(|&n| n != 1)
             .collect::<Vec<_>>()
}

有了这个,我得到了基准:

test tests::bench_collatz_functional ... bench:         867 ns/iter (+/- 28)
test tests::bench_collatz_imperative ... bench:         374 ns/iter (+/- 9)
test tests::bench_collatz_iterators  ... bench:         473 ns/iter (+/- 9)
test tests::bench_collatz_recursive  ... bench:         838 ns/iter (+/- 29)

但有趣的是,如果你决定只关心大小,那么调用:Compose::new(n, collatz_next).take_while(|&n| n != 1).count() as u64与vec.push(c)在命令式方法中删除行几乎完全相同:

test tests::bench_collatz_imperative ... bench:         162 ns/iter (+/- 6)
test tests::bench_collatz_iterators  ... bench:         163 ns/iter (+/- 4)

Answer 2

这将包含一些实现细节，说明为什么unfoldr有点慢。

\n\n

我提出了一个不同的变体，@breeden 帮助我验证了它是一项改进，使其与性能命令变体相匹配。它确实保留了递归，但我们不能再称它为函数式了.. [^1]

\n\n

fn unfoldr2<F, T>(foo: F, seed: T, vec: &mut Vec<T>)\n    where F: Fn(T) -> Option<(T, T)>\n{\n    if let Some((x, y)) = foo(seed) {\n        vec.push(x);\n        unfoldr2(foo, y, vec)\n    }\n}\n\nfn collatz_next(n: u64) -> u64 {\n    if n % 2 == 0 { n / 2 } else { 3 * n + 1 }\n}\n\npub fn collatz_seq_f(n: u64) -> Vec<u64> {\n    let mut v = Vec::new();\n    unfoldr2(|n| if n == 1 { None } else { Some((n, collatz_next(n))) }, n, &mut v);\n    v\n}\n

\n\n

这里的差异将说明\xe2\x80\x9c与第一个版本\xe2\x80\x9d出了什么问题。在 中unfoldr，有一个 vec 值被携带，而在 中unfoldr2只有一个对向量的可变引用。

\n\n

vec 值有影响unfoldr，您发现它限制了编译器：展开。如果函数发生恐慌，就会发生展开。如果它通过unfoldr函数展开，则必须删除所有局部变量，这意味着vec. 插入一些特殊代码来处理这个问题（称为 \xe2\x80\x9clanding pad\xe2\x80\x9d），并且可能会出现紧急情况的函数调用会插入一条指令，以便在紧急情况下转移到着陆垫。

\n\n

所以在unfoldr：

\n\n

\n
1. 有一个具有析构函数的局部变量，vec
\n
2. 有一个函数调用可能会发生恐慌（vec.push容量溢出恐慌）
\n
3. 有一个着陆垫可以下降vec并恢复展开
\n

\n\n

此外，还有用于移动 Vec 值的代码。（它被复制到堆栈中以供着陆垫代码使用）。

\n\n

unfoldr2没有得到任何神奇的递归到循环优化等，但它的代码仍然较少，因为它不需要处理展开或移动 Vec。

\n\n

[^1]：我们可以通过将 vec.push(x) 想象为流/生成器/输出迭代器的接口，或者只是一个回调来挽救功能吗？

\n