如何避免在 Rust 中克隆一个大整数

Question

我在计算一个数的阶乘时使用了 num::BigUInt 类型来避免整数溢出。

然而，我不得不求助于使用 .clone() 来通过 rustc 的借用检查器。

如何重构阶乘函数以避免多次克隆可能很大的数字？

use num::{BigUint, FromPrimitive, One};

fn main() {
    for n in -2..33 {
        let bign: Option<BigUint> = FromPrimitive::from_isize(n);
        match bign {
            Some(n) => println!("{}! = {}", n, factorial(n.clone())),
            None => println!("Number must be non-negative: {}", n),
        }
    }
}

fn factorial(number: BigUint) -> BigUint {
    if number < FromPrimitive::from_usize(2).unwrap() {
        number
    } else {
        number.clone() * factorial(number - BigUint::one())
    }
}

我尝试在函数定义中使用对 BigUInt 的引用，但出现一些错误，指出 BigUInt 不支持引用。

Answer 1

第一个clone很容易去掉。您正试图在同一个表达式中使用 n 两次，所以不要只使用一个表达式：

print!("{}! = ", n);
println!("{}", factorial(n));

等同于 println!("{}! = {}", n, factorial(n.clone())) 但不会尝试移动 n 并同时使用对它的引用。

第二个clone可以通过改变factorial不递归来移除：

fn factorial(mut number: BigUint) -> BigUint {
    let mut result = BigUint::one();
    let one = BigUint::one();

    while number > one {
        result *= &number;
        number -= &one;
    }

    result
}

然而，这可能看起来不合常理。有一个 range 函数，您可以将其与 for 一起使用，但是，它在内部使用 clone，打败了重点。

Answer 2

我认为将 BigUint 作为参数对阶乘没有意义。 u32 应该够了：

use num::{BigUint, One};

fn main() {
    for n in 0..42 {
        println!("{}! = {}", n, factorial(n));
    }
}

fn factorial_aux(accu: BigUint, i: u32) -> BigUint {
    if i > 1 {
        factorial_aux(accu * i, i - 1)
    }
    else {
        accu
    }
}

fn factorial(n: u32) -> BigUint {
    factorial_aux(BigUint::one(), n)
}

或者如果你真的想保留 BigUint:

use num::{BigUint, FromPrimitive, One, Zero};

fn main() {
    for i in (0..42).flat_map(|i| FromPrimitive::from_i32(i)) {
        print!("{}! = ", i);
        println!("{}", factorial(i));
    }
}

fn factorial_aux(accu: BigUint, i: BigUint) -> BigUint {
    if !i.is_one() {
        factorial_aux(accu * &i, i - 1u32)
    } else {
        accu
    }
}

fn factorial(n: BigUint) -> BigUint {
    if !n.is_zero() {
        factorial_aux(BigUint::one(), n)
    } else {
        BigUint::one()
    }
}

两个版本都不做任何克隆。

Answer 3

如果您使用 ibig::UBig 而不是 BigUint，这些克隆将是免费的，因为 ibig 经过优化，不会从堆中为这么小的数字分配内存。

如何避免在 Rust 中克隆一个大整数

How to avoid cloning a big integer in rust

reference

biginteger

pass-by-reference

rust

borrow-checker