optimization - Rust : functional v imperative approach 中的 Collat​​z 猜想

Question

我想和一些老东西一起玩 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())
}

使用 collat​​z_seq_f 返回一个 Vec 器，其序列以给定数字 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()));
    }
}

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)
    } 
}

我获得了与 collat​​z_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, collat​​z_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)