big-o-test crate

测试中的RAM & CPU黑盒分析

big-O-test crate动态分析算法的 空间 和 时间 资源消耗，允许测试强制执行最大复杂度，防止未注意到的性能退化进入主分支。

浏览文档。

它可以在常规和迭代算法上运行，后者对于测试CRUD操作非常有用。

报告使用 大O符号 （因此得名）发布，并通过对算法的CPU时间 & RAM空间需求随数据量或元素数量的增长进行测量来实现。

通过在 测试 中使用此crate，您通过实际测量来强制执行程序在资源消耗方面的行为，这使您能够在生产中预测资源需求，并在优化过程中提供帮助，因为您可以自由地进行更改，这些更改在空间或时间复杂度引入退化时会导致测试失败。

此外，此crate特别适用于分析复杂执行场景中的复杂算法，当传统的 手动 分析无法进行时：精心设计的 大O性能测试 能够调查/强制执行最坏可接受性能情况、最佳情况和算法在 真实数据 片段上的平均性能。

因此，此crate旨在作为 分析 / 开发工具 与 测试 和 基准测试 一起使用。

常规算法和迭代算法之间有一个区别。后者包括每次调用只操作一个元素的算法，可能适合以下类别

• 那些改变它们操作的数据量，例如插入和删除
• 在固定数据集上运行的操作，例如查询、更新和数据转换（ETL）

提供了一种特殊方法来测试CRUD操作，因为它们应遵循特殊规则以提供准确的测量结果——请参见下面的示例

CRUD测试示例

测试CRUD迭代器算法（每次遍历多次调用，因为单个调用处理单个元素）：

此测试产生的可选测量/分析输出

Vec Insert & Remove (worst case) with ParkingLot CRUD Algorithm Complexity Analysis:
  First Pass (create: 8090µs/+64.42KiB, read: 15254µs/+432.00b, update: 13948µs/+432.00b); Second Pass (create: 22440µs/+64.42KiB, read: 15232µs/+432.00b, update: 13839µs/+432.00b):

'Create' set resizing algorithm measurements:
pass          Δt              Δs            Σn            t⁻
1)        8090µs       +64.42KiB         16384         0.494µs
2)       22440µs       +64.42KiB         32768         1.370µs
--> Algorithm  Time Analysis: O(n)
--> Algorithm Space Analysis: O(1) (allocated: 128.20KiB; auxiliary used space: 656.00b)


'Read' constant set algorithm measurements:
pass          Δt              Δs            Σn            ⊆r            t⁻
1)       15254µs        +432.00b         16384        163840         0.093µs
2)       15232µs        +432.00b         32768        163840         0.093µs
--> Algorithm  Time Analysis: O(1)
--> Algorithm Space Analysis: O(1) (allocated: 208.00b; auxiliary used space: 656.00b)


'Update' constant set algorithm measurements:
pass          Δt              Δs            Σn            ⊆r            t⁻
1)       13948µs        +432.00b         16384        163840         0.085µs
2)       13839µs        +432.00b         32768        163840         0.084µs
--> Algorithm  Time Analysis: O(1)
--> Algorithm Space Analysis: O(1) (allocated: 208.00b; auxiliary used space: 656.00b)


Delete Passes (2nd: 23365µs/+432.00b; 1st: 7744µs/+432.00b) r=262144:
'Delete' set resizing algorithm measurements:
pass          Δt              Δs            Σn            t⁻
1)        7744µs        +432.00b         16384         0.473µs
2)       23365µs        +432.00b         32768         1.426µs
--> Algorithm  Time Analysis: O(n)
--> Algorithm Space Analysis: O(1) (allocated: 208.00b; auxiliary used space: 656.00b)

常规算法示例

常规非迭代器算法在每次遍历时只运行一次——下面的示例中，此算法是 vec::sort()

此测试产生的可选测量/分析输出

Running 'Quicksort a reversed vec' algorithm:
  Resetting: 3406857µs/+768.00MiB; Pass 1: 658484µs/76.29MiB; Pass 2: 1315255µs/152.59MiB

'Quicksort a reversed vec' regular-algorithm measurements:
pass          Δt              Δs             n            s⁻           t⁻
1)      658484µs        76.29MiB      40000000            2b         0.016µs
2)     1315255µs       152.59MiB      80000000            2b         0.016µs
--> Algorithm  Time Analysis: O(n)
--> Algorithm Space Analysis: O(n) (allocated: 0.00b; auxiliary used space: 228.88MiB)

在项目中的使用

将其添加到您的 Cargo.toml

[dev-dependencies]
ctor = "0.1"
big-o-test = "0.2"

然后创建一个集成测试，将其设置为按顺序执行测试（使用单个线程）——有关如何轻松实现此操作的示例，请参见 tests/big_o_tests.rs

注意，禁用Rust的默认并行测试运行程序对于准确测量时间和内存至关重要——尽管如此，仍特别小心以避免测试不稳定：当时间复杂度分析不匹配最大接受值时，将启动自动重试机制。

注意

为了测量空间资源需求，此crate设置了一个自定义全局分配器，可以收集分配指标。它仅影响测试，但仍然产生了不可忽视的开销——每次分配/释放都会更新一打原子计数器。