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

debugcn 发表于 Dev

编译器

在带有模板元编程的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; }

但就锈而言，据我所知，您不能仅将常量传递给泛型，而且我知道有时锈会将某些函数优化为汇编代码中的常量。示例：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

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

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

此时，我只想知道为什么会这样。

马修M.

算法复杂度

计算斐波那契数列的幼稚方式具有指数复杂性

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评估。他们不具有对，这是严格意义上的实现细节，但他们出于效率的考虑做。

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

在Rust中做！

可以在编译时使用当前beta计算Rust中的斐波那契，从而稳定const函数中的分支。

参观游乐场：

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不会执行递归调用。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。