SMAWK算法在Rust中的实现

此crate包含了一个SMAWK算法的实现，用于在单调递增矩阵中找到每行的最小元素。

SMAWK算法可以将某些算法的运行时间从O(n²)降低到O(n)。换句话说，您可以将二次时间复杂度（通常成本很高）转换为线性时间复杂度。

在文本段落中找到最佳行断点是这类算法的一个示例，通常对于n个单词，它将花费O(n²)的时间。使用此crate，运行时间将变为线性。请参阅textwrap crate以获取示例。

用法

将以下内容添加到您的 Cargo.toml

[dependencies]
smawk = "0.3"

您现在可以高效地找到行和列的最小值。以下是一个找到列最小值的示例

use smawk::Matrix;

let matrix = vec![
    vec![3, 2, 4, 5, 6],
    vec![2, 1, 3, 3, 4],
    vec![2, 1, 3, 3, 4],
    vec![3, 2, 4, 3, 4],
    vec![4, 3, 2, 1, 1],
];
let minima = vec![1, 1, 4, 4, 4];
assert_eq!(smawk::column_minima(&matrix), minima);

minima向量给出每列最小值的索引，所以minima[0] == 1，因为第一列的最小值是2（第1行）。注意，返回的是最小的行索引。

Cargo功能

此crate有一个可选依赖项ndarray crate，它提供了一个高效的矩阵实现。启用ndarray Cargo功能以使用它。

文档

API文档

变更日志

版本0.3.2（2023-09-17）

此版本添加了更多文档，并重命名了顶级SMAWK函数。旧名称目前保留以确保向后兼容性，但它们将在未来的版本中删除。

• #65：禁止使用不安全代码。
• #69：迁移到Rust 2021版。
• #73: 为所有函数添加示例。
• #74: 将“数学”添加为crate类别。
• #75: 从优化函数中删除 smawk_ 前缀。

版本 0.3.1（2021-01-30）

本版本放宽了 smawk_row_minima、smawk_column_minima 和 online_column_minima 函数的限制，使它们能够在包含浮点数的矩阵上工作。

• #55: 将限制放宽到 PartialOrd 而不是 Ord。
• #56: 将依赖项更新到最新版本。
• #59: 在README中给出SMAWK的示例。

版本 0.3.0（2020-09-02）

本版本通过将 ndarray 作为可选依赖项来显著缩小crate的大小。

• #45: 将非SMAWK代码和单元测试从lib移动到单独的模块。
• #46: 将 smawk_row_minima 和 smawk_column_minima 函数切换到新的 Matrix 特性。
• #47: 将对 ndarray crate 的依赖项设置为可选。
• #48: 让 is_monge 接受 Matrix 参数，而不是 ndarray::Array2。
• #50: 删除对 rand 和 num-traits crate 的强制依赖。

版本 0.2.0（2020-07-29）

本版本将代码更新到Rust 2018。

• #18: 使 online_column_minima 在矩阵类型上是泛型的。
• #23: 切换到 Rust 2018 版本。我们将测试最新的稳定版和夜间版Rust。
• #29: 通过不使用Rust 1.31.0进行测试来放弃严格的Rust 2018兼容性。
• #32: 修复 is_monge 中的溢出崩溃。
• #33: 将 rand 依赖项更新到最新版本，并淘汰 rand_derive。
• #34: 将 num-traits 和 version-sync 依赖项更新到最新版本。
• #35: 删除不必要的Windows测试。假设我们进行的数值计算是跨平台的。
• #36: 将 ndarray 依赖项更新到最新版本。
• #37: 自动发布到crates.io的新版本。

版本 0.1.0 — 2018年8月7日

这是第一个版本，其中包含经典的离线SMAWK算法以及一个更新的在线版本，其中矩阵项可以依赖于之前计算过的列最小值。

许可

SMAWK可以根据 MIT许可 进行分发。贡献将接受相同的许可。