budshome (blog: 芽之家) shared the aphorism --
问题的复杂性不在于问题本身,而是找到问题后,你如何去处理。 -- 佚名

[Rust] Rust 纪元第 382 周最佳 crate:ibig 的实践,以及和 num crate 的比较

💥 内容涉及著作权,均归属作者本人。若非作者注明,默认欢迎转载:请注明出处,及相关链接。

Summary: Rust 纪元第 382 周,评出的周最佳 crate 是大数计算方面的 `ibig`。结合目前使用较广的大数计算 crate `num`,采用 2 种阶乘的不同实现方式,进行实践。

Topics: rust crate

Rust 纪元第 382 周,评出的周最佳 crate 是大数计算相关的 ibig。目前在 github 星星数量不足 50,还处于开发初期。

虽然以前的 Rust 开发中,大数计算方面使用的是 num crate 的 BigIntBigUint,完全满足需求。但是查阅到 ibig 提供的基准测试,性能挺不错。所以本文结合目前使用较广的大数计算 crate num,采用 2 种阶乘的不同实现方式,进行实践。尝试一下,看是否进行 crate 替换。

大数计算的概念,就不赘述。我们设想一个 1000000000 甚至更大的阶乘,不使用大数计算相关 crate,显然是跑不起来的。下面,我们使用 numibig 进行测试和比较。

准备

为了仅测试 numibig,我们创建一个单独的工程,并引入 chrono 进行时间的简单计算。执行如下命令:

cargo new bigint
cd ./bigint
cargo add num ibig chrono

阶乘测试和比较

第一种阶乘实现方式

如上一步所示,我们使用的都是最新版本。下面,我们进行阶乘编码的实现,采用两种方式编写。先看第一种:

use chrono::prelude::*;
use ibig::prelude::*;
use num::bigint::{BigInt, ToBigInt};

fn factorial_num1(x: u32) -> BigInt {
    if let Some(mut factorial) = 1.to_bigint() {
        for i in 1..(x + 1) {
            factorial = factorial * i;
        }
        factorial
    } else {
        panic!("阶乘计算失败");
    }
}

fn factorial_ibig1(x: u32) -> UBig {
    if let Some(mut factorial) = Some(UBig::from(1 as u16)) {
        for i in 1..(x + 1) {
            factorial = factorial * UBig::from(i);
        }
        factorial
    } else {
        panic!("阶乘计算失败");
    }
}

fn main() {
    let n: u32 = 100;

    // num crate 大数计算
    let start_num: DateTime<Local> = Local::now();
    println!("{}! 阶乘,num crate 计算: {:#x}", n, factorial_num1(n));

    let end_num: DateTime<Local> = Local::now();
    let time_num = end_num - start_num;

    println!("{:?}", &time_num);

    // ibig-rs crate 大数计算
    let start_ibig: DateTime<Local> = Local::now();
    println!("{}! 阶乘,ibig crate 计算: {:#x}", n, factorial_ibig1(n));

    let end_ibig: DateTime<Local> = Local::now();
    let time_ibig = end_ibig - start_ibig;

    println!("{:?}", &time_ibig);

    // ibig-rs 是否更快?
    println!("ibig-rs 快了这么多:{:#?}", time_num - time_ibig);
}

我们以发布模式命令 cargo run --release 执行计算,返回结果大抵如下所示(secs 正值时表示 num 慢,否则快):

cargo run --release

100! 阶乘,num crate 计算: 0x1b30964ec395dc24069528d54bbda40d16e966ef9a70eb21b5b2943a321cdf10391745570cca9420c6ecb3b72ed2ee8b02ea2735c61a000000000000000000000000
Duration { secs: 0, nanos: 1093700 }

100! 阶乘,ibig crate 计算: 0x1b30964ec395dc24069528d54bbda40d16e966ef9a70eb21b5b2943a321cdf10391745570cca9420c6ecb3b72ed2ee8b02ea2735c61a000000000000000000000000
Duration { secs: 0, nanos: 343900 }

ibig-rs 快了这么多:Duration {
    secs: 0,
    nanos: 749800,
}

因为 100 以上的阶乘中,计算结果非常大,非常占页面空间,所以本文页面就不做结果展示。如果感兴趣,请你通过修改 n 值,进行测试。

笔者的测试结果,在 1000 以下的阶乘中,ibig 确实是快了一些,但没有超过 1 秒。在 10000 时,互有领先,总体来说 num 还是性能占优,和 ibig 相比大约 7:3 的优势。当 100000 时,num 会快到 4 秒左右;大于 100000 及以后,运行很慢,笔者只跑了一次,测试结果不具实际意义。

第二种阶乘实现方式

编码方式的不同,对于性能也有一定的影响,所以细读 ibig 的文档后,进行了第二种阶乘实现:

use chrono::prelude::*;
use ibig::prelude::*;
use num::bigint::{BigInt, ToBigInt};

fn factorial_num2(a: u32, b: u32) -> BigInt {
    if b == a + 1 {
        a.to_bigint().unwrap()
    } else {
        let mid = a + (b - a) / 2;
        factorial_num2(a, mid) * factorial_num2(mid, b)
    }
}

fn factorial_ibig2(a: u32, b: u32) -> UBig {
    if b == a + 1 {
        UBig::from(a)
    } else {
        let mid = a + (b - a) / 2;
        factorial_ibig2(a, mid) * factorial_ibig2(mid, b)
    }
}

fn main() {
    let n: u32 = 100000;

    // num crate 大数计算
    let start_num: DateTime<Local> = Local::now();
    println!(
        "{}! 阶乘,num crate 计算: {:#x}",
        n,
        factorial_num2(1, n + 1)
    );

    let end_num: DateTime<Local> = Local::now();
    let time_num = end_num - start_num;

    println!("{:?}", &time_num);

    // // ibig-rs crate 大数计算
    let start_ibig: DateTime<Local> = Local::now();
    println!(
        "{}! 阶乘,ibig crate 计算: {:#x}",
        n,
        factorial_ibig2(1, n + 1)
    );

    let end_ibig: DateTime<Local> = Local::now();
    let time_ibig = end_ibig - start_ibig;

    println!("{:?}", &time_ibig);

    // ibig-rs 是否更快?
    println!("ibig-rs 快了这么多:{:#?}", time_num - time_ibig);
}

我们同样以发布模式命令 cargo run --release 执行计算,返回结果大抵和第一种方式类同。

但是性能比较,有了变化。在 10000 以下时,ibig 同样是占优的。在 10000 这个阶乘层次,第 1、2 个 10 次都是 5:5,第 3 个 10 次 num 快了一次。100000 及以上,等待时间过长,笔者只跑了一次,测试结果不具实际意义。

所以,目前所使用的 crate num 暂时还是不考虑替换了。

ibig 官方的基准测试

最后,附上 ibig 官方的基准测试值:每个基准测试运行 5 次,每次重复计算至少 10 秒,结果使用中位数运行。

LibraryVersionNotese 100ke 1me 10mfib 1mfib 10mfib_hex 10m
rug1.11.0Links to GMP0.0160.2964.5200.0150.3360.060
rust-gmp0.5.0Links to GMP0.0170.3044.5850.0170.3360.060
ibig0.2.1Pure Rust0.0310.97330.7490.0371.2520.279
ramp0.5.9Uses assembly (requires nightly)0.13512.4871233.2250.35534.8470.386
num-bigint0.4.0Pure Rust0.32531.0063098.5111.161115.2340.401

正如前文笔者所述,代码的不同,平台的不同等,测试性能差别有可能也很大。所以这个基准测试结果,仅能参考。所谓实践出真知,还需要自己实际使用后,才晓得是否合适。

谢谢您的阅读。


Rust 生态与实践

Related Articles

  1. [Rust] Rust 官方周报 395 期(2021-06-16)
  2. [Rust] Rust 1.53.0 明日发布,关键新特性一瞥
  3. [Rust] 使用 tide、handlebars、rhai、graphql 开发 Rust web 前端(3)- rhai 脚本、静态/资源文件、环境变量等
  4. [Rust] 使用 tide、handlebars、rhai、graphql 开发 Rust web 前端(2)- 获取并解析 GraphQL 数据
  5. [Rust] 使用 tide、handlebars、rhai、graphql 开发 Rust web 前端(1)- crate 选择及环境搭建
  6. [Rust] Rust 官方周报 394 期(2021-06-09)
  7. [Rust] Rust web 前端库/框架评测,以及和 js 前端库/框架的比较
  8. [WebAssembly] Rust 和 Wasm 的融合,使用 yew 构建 web 前端(4)- 获取 GraphQL 数据并解析
  9. [WebAssembly] Rust 和 Wasm 的融合,使用 yew 构建 web 前端(3)- 资源文件及小重构
  10. [WebAssembly] Rust 和 Wasm 的融合,使用 yew 构建 WebAssembly 标准的 web 前端(2)- 组件和路由
  11. [WebAssembly] Rust 和 Wasm 的融合,使用 yew 构建 WebAssembly 标准的 web 前端(1)- 起步及 crate 选择
  12. [Rust] Rust 官方周报 393 期(2021-06-02)
  13. [Rust] Rust 官方周报 392 期(2021-05-26)
  14. [Rust] Rust 中,对网址进行异步快照,并添加水印效果的实践
  15. [Rust] Rust 官方周报 391 期(2021-05-19)
  16. [Rust] Rust,风雨六载,砥砺奋进
  17. [Rust] 为什么我们应当将 Rust 用于嵌入式开发?
  18. [Rust] Rust 官方周报 390 期(2021-05-12)
  19. [Rust] Rust + Android 的集成开发设计
  20. [Rust] Rust 1.52.1 已正式发布,及其新特性详述
  21. [Rust] 让我们用 Rust 重写那些伟大的软件吧
  22. [Rust] Rust 1.52.0 已正式发布,及其新特性详述
  23. [Rust] Rust 官方周报 389 期(2021-05-05)
  24. [GraphQL] 基于 actix-web + async-graphql + rbatis + postgresql / mysql 构建异步 Rust GraphQL 服务(4) - 变更服务,以及小重构
  25. [Rust] Rust 1.52.0 稳定版预发布测试中,关键新特性一瞥
  26. [Rust] Rust 生态中,最不知名的贡献者和轶事
  27. [Rust] Rust 基金会迎来新的白金会员:Facebook
  28. [Rust] Rustup 1.24.1 已官宣发布,及其新特性详述
  29. [Rust] Rust 官方周报 388 期(2021-04-28)
  30. [Rust] Rust 官方周报 387 期(2021-04-21)
  31. [GraphQL] 构建 Rust 异步 GraphQL 服务:基于 tide + async-graphql + mongodb(4)- 变更服务,以及第二次重构
  32. [Rust] Rustup 1.24.0 已官宣发布,及其新特性详述
  33. [Rust] basedrop:Rust 生态中,适用于实时音频的垃圾收集器
  34. [Rust] Rust 编译器团队对成员 Aaron Hill 的祝贺
  35. [Rust] Jacob Hoffman-Andrews 加入 Rustdoc 团队
  36. [机器人] 为什么应将 Rust 引入机器人平台?以及机器人平台的 Rust 资源推荐
  37. [Rust] rust-lang.org、crates.io,以及 docs.rs 的管理,已由 Mozilla 转移到 Rust 基金会
  38. [Rust] Rust 官方周报 386 期(2021-04-14)
  39. [Rust] Rust 编译器(Compiler)团队 4 月份计划 - Rust Compiler April Steering Cycle
  40. [GraphQL] 基于 actix-web + async-graphql + rbatis + postgresql / mysql 构建异步 Rust GraphQL 服务(3) - 重构
  41. [Rust] 头脑风暴进行中:Async Rust 的未来熠熠生辉
  42. [GraphQL] 基于 actix-web + async-graphql + rbatis + postgresql / mysql 构建异步 Rust GraphQL 服务(2) - 查询服务
  43. [GraphQL] 基于 actix-web + async-graphql + rbatis + postgresql / mysql 构建异步 Rust GraphQL 服务 - 起步及 crate 选择
  44. [Rust] Rust 2021 版本特性预览,以及工作计划
  45. [Rust] Rust 用在生产环境的 42 家公司
  46. [Rust] 构建最精简的 Rust Docker 镜像
  47. [Rust] Rust 官方周报 385 期(2021-04-07)
  48. [Rust] 使用 Rust 做异步数据采集的实践
  49. [Rust] Android 支持 Rust 编程语言,以避免内存缺陷
  50. [Rust] Android 平台基础支持转向 Rust
  51. [Rust] Android 团队宣布 Android 开源项目(AOSP),已支持 Rust 语言来开发 Android 系统本身
  52. [Rust] RustyHermit——基于 Rust 实现的下一代容器 Unikernel
  53. [Rust] Rustic:完善的纯粹 Rust 技术栈实现的国际象棋引擎,多平台支持(甚至包括嵌入式设备树莓派 Raspberry Pi、Buster)
  54. [Rust] Rust 迭代器(Iterator trait )的要诀和技巧
  55. [Rust] 使用 Rust 极致提升 Python 性能:图表和绘图提升 24 倍,数据计算提升 10 倍
  56. [Rust] 【2021-04-03】Rust 核心团队人员变动
  57. [Rust] Rust web 框架现状【2021 年 1 季度】
  58. [Rust] Rust 官方周报 384 期(2021-03-31)
  59. [Rust] Rust 中的解析器组合因子(parser combinators)
  60. [生活] 毕马威(KPMG)调查报告:人工智能的实际采用,在新冠疫情(COVID-19)期间大幅提升
  61. [Python] HPy - 为 Python 扩展提供更优秀的 C API
  62. [Rust] 2021 年,学习 Rust 的网络资源推荐(2)
  63. [Rust] 2021 年,学习 Rust 的网络资源推荐
  64. [生活] 况属高风晚,山山黄叶飞——彭州葛仙山露营随笔
  65. [Rust] Rust 1.51.0 已正式发布,及其新特性详述
  66. [Rust] 为 Async Rust 构建共享的愿景文档—— Rust 社区的讲“故事”,可获奖
  67. [Rust] Rust 纪元第 382 周最佳 crate:ibig 的实践,以及和 num crate 的比较
  68. [Rust] Rust 1.51.0 稳定版本改进介绍
  69. [Rust] Rust 中将 markdown 渲染为 html
  70. [生活] 国民应用 App 的用户隐私数据窥探
  71. [GraphQL] 构建 Rust 异步 GraphQL 服务:基于 tide + async-graphql + mongodb(3)- 重构
  72. [GraphQL] 构建 Rust 异步 GraphQL 服务:基于 tide + async-graphql + mongodb(2)- 查询服务
  73. [GraphQL] 构建 Rust 异步 GraphQL 服务:基于 tide + async-graphql + mongodb(1)- 起步及 crate 选择
  74. [Rust] Rust 操控大疆可编程 tello 无人机

Topics

rust(73)

graphql(16)

rust-官方周报(12)

webassembly(9)

async-graphql(8)

rust-官方博客(8)

tide(7)

rust-web(7)

wasm(6)

this-week-in-rust(6)

yew(6)

mysql(5)

rbatis(5)

android(4)

actix-web(4)

mongodb(3)

json-web-token(3)

jwt(3)

cargo(3)

技术延伸(3)

trunk(3)

handlebars(3)

rhai(3)

用户隐私(2)

学习资料(2)

python(2)

ai(2)

人工智能(2)

postgresql(2)

rust-compiler(2)

rust-基金会(2)

rust-foundation(2)

rustup(2)

rust-toolchain(2)

rust-工具链(2)

rust-游戏开发(2)

rust-区块链(2)

graphql-client(2)

tello(1)

drone(1)

无人机(1)

隐私数据(1)

markdown(1)

html(1)

crate(1)

async(1)

异步(1)

旅游(1)

不忘生活(1)

葛仙山(1)

hpy(1)

python-扩展(1)

正则表达式(1)

解析器组合因子(1)

组合器(1)

regular-expression(1)

parser-combinator(1)

regex(1)

官方更新(1)

rust-工作招聘(1)

rust-技术资料(1)

rust-周最佳-crate(1)

rust-web-框架(1)

rust-web-framework(1)

rust-核心团队(1)

rust-core-team(1)

rust-language-team(1)

pyo3(1)

rust-python-集成(1)

python-性能改进(1)

迭代器(1)

iterator-trait(1)

国际象棋(1)

chess(1)

游戏引擎(1)

game-engine(1)

虚拟化(1)

unikernel(1)

rustyhermit(1)

linux(1)

virtualization(1)

sandboxing(1)

沙箱技术(1)

数据采集(1)

异步数据采集(1)

docker(1)

镜像(1)

生产环境(1)

rust-评价(1)

rust-2021-edition(1)

rust-2021-版本(1)

graphql-查询(1)

vision-doc(1)

愿景文档(1)

代码重构(1)

steering-cycle(1)

方向周期(1)

隐私声明(1)

机器人(1)

robotics(1)

rustdoc(1)

rust-编译器(1)

实时音频(1)

real-time-audio(1)

变更服务(1)

mutation(1)

查询服务(1)

query(1)

rust-贡献者(1)

rust-轶事(1)

rust-稳定版(1)

rust-预发布(1)

rust-测试(1)

安全编程(1)

可信计算(1)

安全代码(1)

secure-code(1)

rust-android-integrate(1)

rust-embedded(1)

rust-嵌入式(1)

rust-生产环境(1)

rust-2021(1)

rust-production(1)

网页快照(1)

网页截图(1)

水印效果(1)

图片水印(1)

rust-wasm(1)

yew-router(1)

css(1)

web-前端(1)

wasm-bindgen(1)

区块链(1)

blockchain(1)

surf(1)

dotenv(1)

标识符(1)

rust-1.53.0(1)

Elsewhere

- Open Source
  1. github/zzy
  2. github/sansx
- Awesome Blog
  1. Sansx's Studio
  2. 曙光磁铁的博客
- Learning & Studying
  1. Rust 学习资料 - 芽之家