generics - 使用泛型在编译时生成斐波那契数列

Question

关闭。这个问题需要更多 focused .它目前不接受答案。












想改进这个问题？更新问题，使其仅关注一个问题 editing this post .

1年前关闭。




Improve this question




在带有模板元编程的 C++ 中，您可以通过这种方式轻松地在编译时计算斐波那契数列。

template<int  N>
constexpr int fibonacci() {return fibonacci<N-1>() + fibonacci<N-2>(); }
template<>
constexpr int fibonacci<1>() { return 1; }
template<>
constexpr int fibonacci<0>() { return 0; }

但是据我所知，在 rust 中，你不能只通过泛型传递一个常量，我也知道有时 rust 会将一些函数优化为汇编代码中的常量。示例: https://rosettacode.org/wiki/Compile-time_calculation#Rust
但是问题的传统递归方法并没有优化到一个常数。

fn fibo(n: i32) -> i32 {
    match n {
        0 => 0,
        1 => 1,
        n => fibo(n - 1) + fibo(n - 2),
    }
}

// Call it with
fibo(45); // It takes around 5 secs, calculated at runtime

好的，到目前为止，我可以理解只是编译器不知道如何优化它，但我找到了一种在编译时使用迭代器计算它的方法!

struct Fibo(u32, u32);

impl Iterator for Fibo {
    type Item = u32;
    fn next(&mut self) -> Option<Self::Item> {
        *self = Fibo(self.1, self.1 + self.0);
        Some(self.0)
    }
}

fn fibo() -> Fibo {
    Fibo(0, 1)
}

// Call it with
fibo().take(45).collect::<Vec<_>>()[44]; // This gets the 45th element calculated at compile-time, instantly

在这一点上，我只想知道为什么会发生这种情况。

Answer 1

算法复杂度
计算斐波那契数列的简单方法具有指数复杂性

fn fibo(n: i32) -> i32 {
    match n {
        0 => 0,
        1 => 1,
        n => fibo(n - 1) + fibo(n - 2),
    }
}

您可以将其可视化为:

fibo(0) : 1 次通话。

fibo(1) : 1 次通话。

fibo(2) : 3 次通话 -- fibo(2) , fibo(1) , fibo(0) .

fibo(3) : 5 次通话 -- fibo(3) , fibo(2) (值(value) 3)，fibo(1) .

fibo(4) : 9 次通话 -- fibo(4) , fibo(3) (值(value) 5)和 fibo(2) (值(value) 3)。

然而，迭代器版本完全不同。重写为一个函数，它归结为:

fn fibo(n: i32) -> i32 {
    fn rec(i: i32, current: i32, next: i32) -> i32 {
        if i == 0 { current } else { rec(i - 1, next, current + next) }
    }

    rec(n, 0, 1)
}

恰好在 n + 1 中执行步骤...提供 n >= 0 .
但在 C++ 中它可以工作!
C++ 编译器倾向于对模板实例化和 constexpr 评估使用内存。他们不必这样做，这严格来说是一个实现细节，但出于效率原因，他们这样做了。
在这种情况下， fibo 的内存版本将指数复杂度转化为线性复杂度，这更容易计算。
用 Rust 做!
可以在编译时使用当前 beta 计算 Rust 中的斐波那契，这可以稳定 const 中的分支职能。
见 the playground :

const fn fibo(n: i32) -> i32 {
    const fn rec(i: i32, current: i32, next: i32) -> i32 {
        if i == 0 { current } else { rec(i - 1, next, current + next) }
    }

    rec(n, 0, 1)
}

fn main() {
    const RESULT: usize = fibo(9) as usize;

    let array: [i32; RESULT] = [
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
        0, 1
    ];
    
    println!("{}", array[0]);
}

可能有一个技巧可以在没有分支的情况下在编译时表达计算，允许计算 fibo在稳定的编译时，但是我不确定 rustc 无论如何都不会执行递归调用。