如何避免在 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 经过优化，不会从堆中为这么小的数字分配内存。

Answer 4

任务是避免

.clone

，并且对 OP 解决方案进行尽可能最小的更改，如下所示：

fn factorial(number: BigUint) -> BigUint {
    if number < FromPrimitive::from_usize(2).unwrap() {
        BigUint::one()  // 0! == 1
    } else {
        (&number) * factorial(&number - BigUint::one())
    }
}

游乐场