Utote

高性能，在 Rust stable 上实现的栈分配 uint 多集合，支持使用 Rust nightly 的 SIMD 实现。

最低支持的 Rust 版本：1.51

文档

示例

use utote::Multiset;

// A multiset of 5 elements, which can be counted up to u8::MAX
let mut multiset = Multiset::from([0u8, 3, 4, 0, 5]);
assert_eq!(multiset.total(), 12);

let equivalent_multiset = Multiset::<u8, 5>::from([0, 3, 4, 0, 5]);
assert_eq!(multiset, equivalent_multiset);

multiset.insert(2, 6);
assert_eq!(multiset, Multiset::from([0, 3, 6, 0, 5]));

for elem in multiset.iter() {
    println!("{}", elem);
}

assert_eq!(multiset.contains(0), false);
assert_eq!(multiset.contains(1), true);

一些常见的集合操作

use utote::Multiset;

let ms_sub: Multiset<u32, 3> = Multiset::from([0, 1, 1]);
let ms_super = Multiset::from([1, 1, 2]);

assert_eq!(ms_sub.is_subset(&ms_super), true);

assert_eq!(ms_sub.union(&ms_super), Multiset::from([1, 1, 2]));

assert_eq!(ms_super.is_proper_superset(&ms_sub), true);

// Any multiset where all counters are zero is equivalent to
// the empty multiset.
let empty: Multiset<u64, 2> = Multiset::from([0, 0]);
assert_eq!(empty, Multiset::empty());

实现说明

Utote 多集合具有一个单一的泛型 API，但提供了多个等价的标量和 SIMD 函数实现，其中 SIMD 可以提高性能。SIMD 功能仅在 nightly 版本中可用，而标量版本可以在 stable 版本中使用。

仅在 nightly 版本中使用的 SIMD 实现使用了 packed_simd 以及不稳定特性：const_generics 和 const_evaluatable_checked（所有特性都位于 "simd" 特性标志之后）。由于其简单性以及假设当 std::simd 稳定下来时，其 API 结构将类似于现在的 packed_simd，因此选择了 packed_simd 而不是其他替代方案。

一旦 const generics 和可移植 SIMD 支持达到 stable，这个 crate 也将完全稳定。直到这些特性稳定下来，Utote 的版本将保持在 1.0.0 以下。

由于多集合本质上是对计数器的一些有用方法的集合，并且为了保持简单，实现仅适用于 uint 类型。因此，当前的多集合相当底层，可能更适合作为为任何给定类型工作的更高层次多集合的后端。

尽管为 Multiset 实现 Deref<[T]> 是简单的，但我出于两个原因决定不这样做。首先，为了避免在 API 中暗示 Multiset 的方法可以排序计数。由于计数的顺序是实现工作固有的，我想避免任何这种做法是合适的混淆。其次，由于大多数 Multiset 的功能方法最终将在切片上实现，然后从不同的 Multiset 变体中调用，实现到切片的 deref 可能会在代码中造成混淆。

未来开发

• 提供一个堆分配的 MultisetVec 类型，它使用 Vec 而不是数组进行存储。

许可证

许可协议如下之一

• Apache License，版本 2.0，(LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT 协议 (LICENSE-MIT 或 http://opensource.org/licenses/MIT）

任选其一。

贡献

除非您明确声明，否则您提交的任何贡献，包括 Apache-2.0 许可证中定义的，都将双重许可，如上所述，没有附加条款或条件。

致谢

本库中的实现受到了 generic-array、nalgebra 和 simba 的启发。

变更日志

0.6.0（重大变更）

• API 变更
  • 重命名 Multiset::argmax 为 Multiset::elem_count_max
  • 重命名 Multiset::argmin 为 Multiset::elem_count_min
  • 重命名 Multiset::imax 为 Multiset::elem_max
  • 重命名 Multiset::imin 为 Multiset::elem_min
  • 重命名 Multiset::max 为 Multiset::count_max
  • 重命名 Multiset::min 为 Multiset::count_min
• 清理并扩展文档
• 确保 PartialOrd 实现使用最有效的方法
• 添加从 Multiset 引用到 From 的实现
• 修复 is_any_lesser 和 is_any_greater 的 simd 实现
• 删除不必要的 SmallRng 使用

0.5.0（重大变更）

• 提供统一的泛型接口
• 重新实现标量和 simd 后端
• 删除所有类型别名
• 从 API 中删除所有 simd 类型/考虑因素
• 删除一些 const 构造函数以启用稳定的泛型接口
• 改进文档
• 添加 Rem 操作符
• 添加广播算术操作符
• 添加 From 实现
• 完成 FromIterator 和 IntoIterator 的实现覆盖
• 添加 Index 和 IndexMut 实现
• 简化多个函数
• 添加函数
  • difference
  • symmetric_difference
  • from_elements
  • is_disjoint
  • get_mut
  • get_unchecked_mut
• 添加检测到的 CPU 特性上的动态分派，目前支持
  • AVX2
  • AVX
  • SSE4.2