java - 更新分位数而不是重新计算

Question

是否有一个 Java 库允许我通过添加/删除数据点来更新而不是重新计算大型样本数据集的分位数？我的猜测是，高效的算法应该花费恒定的时间进行更新(而不是现有点数的函数)。

列出了已知算法，但没有从样本集中删除点的方法:

• Colt Stream Quantiles :这个一旦添加数据就无法删除
• Apache Math Percentile :这个只是计算数组的分位数，无法从数组中删除数据。

这是一个示例问题:假设我想计算一组风车的任意但恒定的百分位数风扇速度(作为风速的估计)。风扇速度每隔几毫秒异步更新一次。这个库应该允许我一次更新一台风车的风速，而不必重新计算中值。

Answer 1

如果您维护数据的可更新排序表示，则只需使用数组的长度即可轻松高效地获取分位数。例如，如果有 N 个元素，则中位数将位于位置 N/2，依此类推。当您将新元素插入数据结构时，这仍然有效。效率仅取决于插入新元素。