中位数累积器

简单、空间高效的计算元素累积中位数的算法。

• 单推模式（没有运行窗口）
• 中位数在每次推送时更新（获取中位数始终是 O(1)）
• 空间高效： O(D) 空间，D为不同样本的数量，而不是样本的 总数
• 时间高效：推送是 O(log(N))
• 泛型： T: Clone + Ord
• 无安全风险
• no_std（可选）：支持泛型集合

如果有很多样本值相同，则比其他实现更快。如果不是这种情况，您应该使用其他实现。

使用

use median_accumulator::*;

let mut acc = vec::MedianAcc::new();

assert_eq!(acc.get_median(), None);
acc.push(7);
assert_eq!(acc.get_median(), Some(MedianResult::One(7)));
acc.push(5);
assert_eq!(acc.get_median(), Some(MedianResult::Two(5, 7)));
acc.push(7);
assert_eq!(acc.get_median(), Some(MedianResult::One(7)));

如果您遇到 unreachable panic，请提交问题或发送电子邮件给我。

no_std

示例（需要 smallvec 功能）

use median_accumulator::*;

let mut acc = MedianAcc::<i32, smallvec::SmallVec<[(i32, u32); 64]>>::new();

对于 Vec 或 SmallVec 之外的其他集合，您必须实现 cc-traits 和 InsertIndex。

许可证

版权所有 2022-2024 Pascal Engélibert (为什么是版权所有？)

本程序是自由软件：您可以按照自由软件基金会发布的GNU Affero通用公共许可证的条款重新分发和/或修改它，许可证版本为3。

本程序以希望对您有用的方式分发，但没有任何保证；甚至没有关于适销性或适用于特定目的的隐含保证。有关详细信息，请参阅GNU Affero通用公共许可证。

您应该已收到GNU Affero通用公共许可证的副本。如果没有，请参阅 https://www.gnu.org/licenses/。