sortbuf -- 内存中对大量项目进行排序的数据结构

此库提供用于在内存中累积大量项目并按升序或降序遍历它们的类型和特质。它优于基于 BTree 的排序，引入了低内存开销，并允许从多个线程插入项目以及在不丢失数据的情况下响应分配失败。然而，它的唯一目的是排序，它不提供其他功能。

示例

let mut sortbuf = sortbuf::SortBuf::new();
let mut inserter = sortbuf::Inserter::new(&mut sortbuf);
inserter.insert_items([10, 20, 5, 17]).expect("Failed to insert items");
drop(inserter);
assert!(sortbuf.into_iter().eq([20, 17, 10, 5]));

许可证

此作品提供在MIT许可证下。有关更多详细信息，请参阅 LICENSE。

lib.rs:

在内存中对大量项目进行排序

此库提供类型，最显著的是 [SortBuf]，以及用于在内存中累积大量项目并在升序或降序（如[Ord]）中遍历它们的特质。实现

• 避免了可能昂贵的重新分配，
• 在迭代期间不时释放内存块，
• 引入的内存开销不大，
• 允许对分配失败做出反应，
• 支持多线程插入，
• 并且速度并不慢。

示例

默认情况下，[SortBuf]将为降序迭代准备项目

let mut sortbuf = sortbuf::SortBuf::new();
let mut inserter = sortbuf::Inserter::new(&mut sortbuf);
inserter.insert_items([10, 20, 5, 17]).expect("Failed to insert items");
drop(inserter);
assert!(sortbuf.into_iter().eq([20, 17, 10, 5]));

对于升序迭代，需要将项目包装在 std::cmp::Reverse 中。然而，该库提供了方便的函数来处理（解）包装

let mut sortbuf = sortbuf::SortBuf::new();
let mut inserter = sortbuf::Inserter::new(&mut sortbuf);
inserter.insert_items_reversed([10, 20, 5, 17]).expect("Failed to insert items");
drop(inserter);
assert!(sortbuf.unreversed().eq([5, 10, 17, 20]));

通过多个 [Inserter] 支持多线程插入

use std::sync::{Arc, Mutex};
let sortbuf: Arc<Mutex<sortbuf::SortBuf<_>>> = Default::default();
let workers: Vec<_> = (0..4).map(|n| {
    let mut inserter = sortbuf::Inserter::new(sortbuf.clone());
    std::thread::spawn(move || inserter
        .insert_items((0..1000).map(|i| 4*i+n))
        .expect("Failed to insert items"))
}).collect();
workers.into_iter().try_for_each(|h| h.join()).unwrap();
assert!(sortbuf.lock().unwrap().take().into_iter().eq((0..4000).rev()));

方法和比较

如上例所示，通过 [Inserter] 将新项目添加到缓冲区。这些在预先排序的 [Bucket] 中累积项目并将它们提交到目标缓冲区。稍后，可以将该缓冲区转换为 [Iterator]，它从那些 [Bucket] 中产生项目，这涉及选择缓冲区中当前最大的项目所在的 [Bucket]。

尽管在插入过程中花费了大量的时间，但通常大部分时间都是在迭代过程中花费的。性能通常更好，并且倾向于在可并行插入状态下花费更多时间，同时拥有更少、更大的 [Bucket]。由于 [Bucket] 是预先分配的，这以牺牲内存的灵活性为代价。

与Vec和sort的比较

也可以使用 [Vec]（用于缓冲）和 slice::sort、slice::sort_unstable 或其他排序函数对项目进行缓冲和排序。然后通常将过程分为插入、排序和迭代阶段，其中排序是计算密集度最高的阶段。

对[Vec]中的元素进行排序和迭代通常比使用本库提供的工具要快——在单线程的情况下。然而，与裸[Vec]不同，本库允许从多个线程进行插入。此外，将项目插入[Vec]的性能取决于重新分配的性能，在某些情况下可能较差，例如涉及多个缓冲区时。

单独、独立的计算密集型排序阶段的需求也可能对某些用例的整体性能产生一些影响。使用本库提供的类型，排序可能会与插入和/或最终迭代的I/O交织在一起，在整个过程中分散。因此，底层操作系统有更多机会执行与读取（插入阶段）和写入（迭代阶段）相关的后台操作，从而提高整体吞吐量。

与BTreeSet的比较

另一个不需要单独排序阶段的排序项选项是BTreeSet。与sortbuf方法不同，大部分时间都花在插入阶段而不是迭代阶段。通常使用BTreeSet比有足够大的[Bucket]的[SortBuf]慢，不可并行化，并且产生更高的内存开销。