Bigoish: Rust算法复杂度实证测试

Rust Testing Performance

评分: ★★★★☆ (4/5)

概述

Bigoish 是一个 Rust 测试库，用于通过实验验证算法的时间复杂度是否符合预期。你是否曾实现了一个新的排序算法，想知道它是否真的是 O(n log n)？有了 bigoish，你可以编写测试来断言特定的经验计算复杂度。

核心功能

• 实证复杂度测试: 通过实际运行测量，验证算法复杂度
• 多模型比较: 自动与常数、线性、二次、三次、平方根、对数等多种模型对比
• 可视化输出: 测试失败时生成图表，直观展示拟合效果
• 无障碍支持: 支持屏幕阅读器禁用可视化

示例代码

use bigoish::{N, Log, assert_best_fit, growing_inputs};

fn sort(mut v: Vec) -> Vec {
    v.sort();
    v
}

fn make_vec(n: usize) -> Vec {
    use fastrand;
    std::iter::repeat_with(|| fastrand::i64(..)).take(n).collect()
}

assert_best_fit(
    N * Log(N),  // 期望复杂度: O(n log n)
    sort,
    growing_inputs(10, make_vec, 25),
);

使用建议

• 使用足够的输入数量 (20个比4个好)
• 输入应跨越多个数量级
• 最小输入规模要足够大，避免噪声
• 在 release 模式下运行测试以获得准确结果

技术细节

• 测量方式: Linux上尝试使用CPU指令计数，失败则回退到CPU时间
• 支持的模型: Constant, Log, N, N², N³, √n, n log n, log log n
• 灵感来源: Python的bigO库，基于Goldsmith等人的论文

链接

• Docs.rs 文档
• Crates.io

来源: Lobsters (performance tag) | 发现日期: 2026-03-27