Tinysort

Tinysort是一个用于尽可能减少内存占用进行数据排序的库。

示例

use tinysort::TinySort;

let mut sort = TinySort::new(8000, 1_000_000, 100_000_000).unwrap();

// create some values to sort between the indicated borders
let mut values: Vec<u32> = (0 .. 1_000_000).map(|i| (100_000_000.0 * (i as f64 * 0.4567895678).fract()) as u32).collect();
for value in values.iter().cloned() {
     sort.insert(value);
}

println!("TinySort using {} bytes of memory, normal sort using {} bytes of memory.", sort.used_space(), values.len() * std::mem::size_of::<u32>());
let sorted: Vec<u32> = sort.into_iter().collect();
values.sort_unstable();
assert!(sorted == values);

此示例将打印TinySort使用1043916字节内存,正常排序使用4000000字节内存.，展示了TinySort带来的近4倍的内存使用下降。

说明

对于排序算法，通常在速度和内存使用之间有一个权衡。对于经典排序算法，我们计算内存使用为算法的额外内存使用，即算法在存储原始值的基础上，需要存储其操作的数据的任何空间。

Tinysort在适用的情况下不需要任何额外内存。事实上，它存储所有排序值的内存比仅仅存储在连续数组中所需的内存还要少。它只需要足够的内存来存储包含的排序值的原始熵，并留出少量用于账簿目的的余地。

这意味着它可以在小于1MiB的内存中排序和存储一百万个介于0到1亿之间的数字。

复杂性

此算法的内存和时间复杂度取决于其输入的两个属性。第一个是它将处理的总值数（N），第二个是输入中包含的最大值（M）

算法的内存使用量按最坏情况为 O(N*log(1+M/N) + M*log(1+N/M))（这确实值得一些荒谬的奖励）

算法的时间复杂度在最坏情况下为 O((N + M)*(Log(N)))