#集合操作 #二分搜索 #排名 #归并排序 #低级 #哈希排序

集合

作为集合的泛型向量。高效排序、合并、排名、搜索、反转、交集等。

23个版本 (14个稳定版)

1.2.1 2023年4月29日
1.2.0 2022年11月13日
1.1.4 2022年10月23日
1.1.1 2022年7月10日
0.1.7 2021年7月10日

#292 in 算法

Download history 183/week @ 2024-03-07 32/week @ 2024-03-14 8/week @ 2024-03-28 3/week @ 2024-04-04

每月97次下载

Apache-2.0

34KB
454

集合 crates.io GitHub last commit Actions Status

作者:Libor Spacek

集合操作,以及高效的排序、排名、搜索等。目标是尽可能避免移动数据。这是通过操作索引来实现的。

此crate定义了Struct: Set,它封装了五种集合类型:空集、无序集、有序集、索引集和排名集,以及作用于它们的函数。这些函数适用于任何原始端类型的泛型向量(或切片)<T>。同时,对于任何任意复杂的用户端类型,只要为它实现了所需的特(由用户实现),也可以使用。它为crate indxvec中的低级方法添加了组织和类型安全。

用法

Cargo.toml文件中,在[dependencies]下插入:sets = "^1"
在源文件中的以下'使用'声明使所有内容可用

use sets::{Set,MutSetOps};

Set<T>

/// The struct type for sets
#[derive(Default)]
pub struct Set<T> {
    /// type of the set
    pub stype: SType,
    /// order: ascending (true), descending (false)
    pub ascending: bool,
    /// data Vec
    pub data: Vec<T>,
    /// index Vec
    pub index: Vec<usize>
}

CloneDisplay特性能为SetSType实现。
Default被推导出来,因此Default::default()生成一个空集。

SType指定五种集合中的一种。它通过'枚举泛型'处理。

/// The five types of sets
#[derive(Default,Clone,Copy)]
pub enum SType {
    /// empty set
    #[default]
    Empty,
    /// unordered set
    Unordered,
    /// ordered set
    Ordered,
    /// indexed set
    Indexed,
    /// ranked set
    Ranked
}

关联初始化器

初始化器与struct Set相关联,因此要调用它们,需要使用::语法,例如:Set::new(..)

    /// all in one Initialiser: creates a new Set
    /// of any self_type SType, from slice d, in asc order 
    pub fn new(set_type: SType, d: &[T], asc:bool) -> Self

对于所有STypes,也存在显式命名的便利函数:new_empty, new_unordered, new_ordered, new_indexed, new_ranked。所有有序类型(即有序、索引、排名)都接受一个bool参数来指定升序或降序。

转换器

    /// General converter - 
    /// converts s to a Set of the same type and order as self 
    /// (self only serves as a template).
    pub fn to_same(&self, s:&Self) -> Self 

同样,我们有显式命名的转换器:to_unordered, to_ordered, to_indexed, to_ranked

   let v = vec![1.,14.,2.,13.,3.,12.];
   let setv = Set::new_unordered(&v);  
   println!("{}",setv); // Display setv 
   // ordered, ascending  
   println!("{}",setv.to_ordered(true)); 
   // indexed, descending
   println!("{}",setv.to_indexed(false)); 

强烈建议阅读并运行tests/tests.rs以获取更多使用示例。使用单个线程运行它们。这可能会稍微慢一些,但会将结果写入正确的顺序

cargo test --release -- --test-threads=1 --nocapture --color always

可以通过点击上面的最后一个徽章并查看其中的自动化测试日志来查看输出。

集合函数

一些通用方法对于有序和索引集合来说更有效率,而不是无序集合。例如,membersearch将自动使用二分搜索。并集类似于经典合并,其中集合之间的重复项被删除。要删除集合内部的重复项,请使用nonrepeat

并集、交集和差集的两个操作数的STypes可以不同。然而,它们需要具有相同的末尾类型<T>。这可能是一种有用的类型纪律。

特质MutSetOps

在这里,方法名称中的'm'代表'mutable'。它们使用结果覆盖它们应用的可变集合。因此,它们不是功能性的,但在处理大型向量的上下文中,它们通常更简单、更高效。当然,这要以破坏self的先前内容为代价。

发行说明(按最新版本排序)

版本1.2.1 - 更新到indxvec 1.8。现在MutSetOps中的闭包参数更简单。它们不再需要是&mut

版本1.2.0 - 更新到indxvec 1.4.9并引入了兼容的泛化。不再需要用户为所有他们的类型T全局实现From特质,而是根据每个单独的使用指定转换闭包。闭包更容易使用,这里它允许使用最有效的hashsort来对集合进行排序。这允许自定义动态转换。请注意,这破坏了之前对morderedmindexedmsame方法的使用。

依赖关系

~95KB