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

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

我查看了您第二个代码示例的汇编输出，编译器似乎没有将其优化为常量。可能发生了一些非常不同的事情。

您称之为“经典”递归算法的方法是计算斐波那契数的最糟糕的方法，因为函数调用的数量随 n 呈指数增长。迭代方法要好得多，因为它只需要随着 n 线性增长的迭代次数。对于 n = 44，递归方法大约需要 10 万亿次函数调用，而迭代方法需要 44 次循环迭代。当然，后者在运行时出现“即时”，但这并不意味着这里发生了任何特定的编译器魔法。

（对于真正大的 n 你需要任意精度的算法，最好的方法是二进制矩阵幂。）

现在回答你的第二个问题，如何让 Rust 在编译时对其求值。 C++ 中的模板元编程实际上是编译时计算的拐杖，而 Rust 有一个更简单的方法：常量函数。 const fns 的某些方面仍在发展中，但在当前的 beta 版本中（大约两周后将作为稳定版本发布），您可以通过相当直接的方式编写 Fibonacci 函数：

pub const fn fibo(mut n: u64) -> u64 {
    let mut a = 1;
    let mut b = 0;
    while n > 0 {
        let tmp = b;
        b += a;
        a = tmp;
        n -= 1;
    }
    b
}

pub const K: u64 = fibo(93);

(Playground)

Rust 中也有 const 泛型，但它们不稳定（而且仍然有很多错误）。有可能你可以做一些类似于C++模板元编程版本的东西，但我没有研究它。

Answer 2

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

此代码将在编译时计算。
但是编译时间比较长，在playground上编译失败。所以rust可能不会优化它。
您还可以看到 the mir 和 ir

Answer 3

算法复杂度

计算斐波那契数列的朴素方法具有指数复杂度

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)（相当于 3 次）、fibo(1).
fibo(4)：9 次通话 -- fibo(4)、fibo(3)（价值 5 次）和 fibo(2)（价值 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 求值使用 memoization。他们没有，这严格来说是一个实施细节，但出于效率原因他们有。

在这种情况下，fibo 的记忆版本将指数复杂度转化为线性复杂度，更容易计算。

用 Rust 做！

可以在 compile-time 的 Rust 中使用当前的 beta 计算斐波那契，这稳定了 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]);
}

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

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

Generate Fibonacci Sequence in Compile-Time using generics

generics

rust

compile-time

算法复杂度

但在 C++ 中它有效！

用 Rust 做！