java - Java 结构，能够确定同时更新的有序集中小于 x 的近似元素数量

Question

假设U是一个有序的元素集，S ⊆ U和x ∈ U。S正在同时更新。我想估计S中在 O(log(| S |) 时间内 小于x的元素数量。

S is being maintained by another software component that I cannot change. However, whenever e is inserted (or deleted) into S I get a message e inserted (deleted). I don't want to maintain my own version of S since memory is limited. I am looking for a structure, ES, (perhaps using O(log(|S|) space) where I can get a reasonable estimate of the number of elements less than any give x. Assume that the entire set S can periodically be sampled to recreate or update ES.

更新：我认为这个问题陈述必须包含更具体的U值。一个明显的情况是U是数字（int、double 等）。另一种情况是U是按字典顺序排列的字符串。

在数字的情况下，可以使用概率分布（但如何确定呢？）。

我想知道是否可以定期扫描集合S。将整个集合放入一个数组并排序。然后在 n/log(n), 2n/log(n) ... n 处选择 log(n) 值，其中 n = | 小号|。然后根据这些值绘制直方图？

更一般地说，如何从S中找到适当的概率分布？

不确定按字典顺序排列的字符串的度量单位是什么？

标签： java

Answer 1

通过concurrently，我假设您的意思是线程安全的。在那种情况下，我相信您正在寻找的是 a ConcurrentSkipListSet，它本质上是一个 concurrent TreeSet。您可以使用ConcurrentSkipListSet#headSet.size()orConcurrentSkipListSet#tailSet.size()获取大于/小于（或等于）单个元素的元素数量，您可以在其中传入 custom Comparator。