java - 一种有效的分位数算法/数据结构,允许样本随着时间的推移而更新?
问题描述
我正在寻找一种有效的分位数算法,该算法允许样本值随着时间的变化而“更新”或替换。
假设我有 items 的值1-n
。我想把这些放到一个分位数算法中,可以有效地存储它们。但是然后说在将来的某个时候,值item-i
会增加。我想删除原始值item-i
并将其替换为更新后的值。特定用例适用于样本值随时间递增的流式系统。
我见过的最接近这种情况的是t-Digest 数据结构。它有效地存储样本值。它唯一缺少的是删除和替换样本值的能力。
我还查看了Apache Quantiles Datasketch - 它遇到了同样的问题 - 无法删除和替换样本。
编辑:更多地考虑这一点,不一定需要删除旧值并插入增量值。如果存在只能更新值的约束,则可能有一种方法可以更轻松地重新计算内部状态。
解决方案
如果您可以接受更新时间O(log n)
和分位数计算时间O(log n)
,那么其中一种解决方案是实现任何类型的自平衡二叉树(Splay 树、AVL-tree、Red-Black 树),同时保持 aHashMap<Key, Node>
与树结构平行(或者如果你知道你的键是数字0
,n-1
那么你可以使用一个数组来达到同样的目的)。您还需要为每个给定节点保留子树中的节点计数(这对于所有提到的自平衡树都是可能的 - 这是对节点进行更新的所有方法的一个小补充,例如旋转, ETC。)。
使用键 K 更新值的伪代码,新值 V 将是:
Node node = find_node_in_hash_map_by_key(K); # O(1)
delete_node_keeping_subtree_counts_valid(node); # O(log n)
add_new_node_keeping_subtree_counts_valid(K, V); # O(log n)
由于每个节点中都有可用的子树大小,因此也可以获取分位数 q O(log n)
,因为它几乎可以让您及时按大小访问第 i 个元素O(log n)
。该操作的伪代码如下所示:
# i-th element requested
node = root
while true:
left = node.left_subtree
left_count = 0
if left is not None:
left_count = left.nodes_count
if i < left_count:
node = left # select i-th element in the left subtree
elif i == left_count:
return node.value # we have exactly i elements in left subtree, so i-th value is in the current node
else:
i -= left_count + 1 # select element i - left_count - 1 from the right subtree
node = node.right
我不知道这种数据结构有一个好的开源 JAVA 解决方案,但是编写自己的 AVL 树并不是那么困难(并且 Splay 树应该是最简单的,只是它们的最坏情况复杂性不是O(log n)
,但平均而言它们应该要好)。
推荐阅读
- windows-10 - Windows 10 主机文件 localhost
- php - 在PHP中定义数组时使用双箭头和单冒号有什么区别
- python - 是否可以部分更改参数值?
- c++ - 无法在屏幕上绘制正方形(相同宽度和高度)
- javascript - 比较js中两个数组的键值
- ios - sonarqube 混合 obj-c swift 项目,如何扫描代码覆盖率
- r - 从决策树中提取变量名称
- javascript - 如何通过具有未知父名称的二级属性过滤json?
- python-3.x - 使用 psycopg2 将列插入 PostgreSQL 时,为什么第一列显示为单词“数据”?
- rest - 无法使用 Angular 7 发布:标题不起作用