高效百分位数查找的数据结构？

Question

假设您有一个大的键/值对集合，其中值是任意实数。您想创建一个支持以下操作的数据结构：

• 插入：向集合中添加新的键/值对，
• 删除：从集合中删除键/值对，
• 百分位数：告诉给定键关联的值在哪个百分位数上，以及
• 告知百分位数：接受一个百分位数并返回具有最低值且至少符合给定百分位数的键。

例如，可以使用此数据结构在接收全国范围内测试成绩流时高效地确定给定学生所属的百分位数，或者识别具有异常良好或不良服务质量的医院。

是否有方法使这些操作运行高效（例如，次线性时间）？

- templatetypedef

---

如果您想每次查找相同的百分位数，可以维护一对堆来保存所需百分位数以上/以下的值。请参见https://dev59.com/xG865IYBdhLWcg3wl_o3#3738476 - Peter Cordes

Answer 1

实现这种数据结构的一种可能方法是使用 顺序统计树 和 哈希表 的混合。

顺序统计树是一种平衡二叉搜索树，除了支持常规的二叉搜索树操作外，还支持两个额外的操作：

• Rank(key)，返回树中小于给定元素的元素数量；
• Select(k)，返回树中第k小的元素。

通过在正常的平衡二叉搜索树（例如 红黑树 或 AVL树）上添加额外的信息来构建顺序统计树。这样，所有顺序统计树上的常规BST操作都可以在 O(log n) 时间内运行，额外的操作也可以在O(log n)时间内运行。

现在，假设你仅存储数值分数，而不是键/百分位分数。在这种情况下，实现百分位查找非常简单，只需将所有值存储在顺序统计树中。要确定给定值的百分位分数，请使用顺序统计树上的rank操作查找该值出现的索引。这会给出一个数字，范围从0到n-1（其中n是树中元素的数量），表示该分数在顺序统计树中的位置。然后可以将该数字乘以99 /（n-1），以获得值的百分位分数，该分数的范围为0到99，如所需。

要确定大于某个百分位数的最低值，您可以使用以下 select 操作。给定一个介于 0 和 99 之间的百分位数，将该百分位数乘以 99 / (n-1) 以得到 0 到 n-1 之间的实数，包括两端。取该数字的上限可产生一个自然数，范围在 0 到 n-1 之间，包括两端。然后，在顺序统计树上使用 select 操作，可以找到第一个处于给定百分位数或以上范围内的值。

但是，这些操作假设我们在数据结构中仅有值，没有键/值对。为了使此操作适用于键/值对，请按以下方式增强数据结构：

1. 与其仅存储值，不如在每个节点中存储键/值对。顺序统计树纯粹按其值对键/值对进行排序，并保留键作为卫星数据。
2. 我们将存储一个二级哈希表，将键映射到其关联的值。

这两个更改使我们能够实现所需的数据结构功能。为了让数据结构通过键执行百分位查找，我们首先使用给定的键查询哈希表以查找其关联值。然后像之前一样在该值上进行百分位查找。为了让数据结构告诉我们一个键，其值是给定百分位数或以上的第一个键，我们在上述有序统计树上执行常规的查找百分位操作，然后查找与给定值相关联的键。

如果我们假设哈希表使用链式哈希，则每个操作所需的时间如下：

• 插入: 在有序统计树中插入值/键对的时间为O(log n)，加上在哈希表中插入键/值对的平均时间为O(1)。总时间为摊销的O(log n)。
• 删除: 从有序统计树中删除值/键对需要O(log n)的时间，再加上从哈希表中删除键/值对的摊销时间为O(1)。总时间为摊销的O(log n)。
• 百分位数: 查找与键相关联的值的期望时间为O(1)，进行排名操作需要O(log n)的时间，并且映射排名到百分位数需要额外的O(1)时间。总时间为期望的O(log n)。
• 查找百分位数: 将百分位数映射到排名所需的时间为O(1)，执行选择操作需要O(log n)的时间。总时间为最坏情况下的O(log n)。

希望这有所帮助！

- templatetypedef

Answer 2

有一个简单而高效的方法：

如果你只需要在最终填充了学生结构体之后搜索百分位数，那么可以使用ArrayList来动态构建，当你不知道元素数量时。如果你知道它们，那么直接从数组开始，否则从动态数组创建数组。(例如Java中的ArrayList)。

插入：不必要，在末尾添加后排序即可。 删除：如果可以接受的话，也不必要。 告诉百分位数：更简单的是：与element[length * percentile]非常接近：O(1)

实际上，在Java中，数组方法比平衡树方法快得多，至少在应用程序可以一次性构建数组的情况下(例如每天对学生进行评估，每天都构建它)。

我已经使用自己编写的ArrayListInt实现了上述算法，它与ArrayList相同，但使用基本类型(double、int)而不是对象类型。当所有数据都被读取时，我会进行一次排序。

此外，你想要键值： 我会添加一个TreeMap(平衡树)。现在这有点值得怀疑，因为TreeMap和额外的百分位数数组是否有意义取决于你需要搜索的频率、内存使用与搜索时间之间的关系。

更新：

结果：treeset与排序数组(动态构建数组，然后最终排序)：

num elements: 1000 treeSet: 4.55989 array=0.564159
num elements: 10000 treeSet: 2.662496 array=1.157591
num elements: 100000 treeSet: 31.642027 array=12.224639
num elements: 1000000 treeSet: 1319.283703 array=140.293312
num elements: 10000000 treeSet: 21212.307545 array=3222.844045

现在的元素数量已经接近限制值（1GB堆空间），在下一步内存将会不足（虽然在清理完TreeSet的内存后，1e7的测试案例也可以正常运行）。

尚缺的是搜索时间，但使用二分查找的排序数组只能被哈希表超越。

最后: 如果您能够构建学生集合，例如每天构建一次，则使用数组方法可以更轻松地进行百分位数搜索。

- AlexWien

---

-1：哎呀，看起来你可能基本上误解了复杂度分析。一个O(N)的方法在特定（小）值的N下可能比一个O(log(N))的方法更快，并不意味着你所说的那样，O(N)方法总是更好。大O分析的整个重点是渐近性能 - 随着N趋向于更大的值，O(log(N))方法将胜过O(N)方法，无论常数/低阶因素如何。 - Darren Engwirda

你真的确定memcopy可以比查找10000个元素的BST树更快地移动它们吗？随着现代内存分配器优化局部性，我非常怀疑这是真的。你能用一些数据或参考来支持吗？ - templatetypedef

@Yikes：我写的是”在实践中总是获胜”，这意味着针对真正的应用场景，而不是针对将MAX_INT元素输入进去的基准测试。此外，不要忘记内存使用情况，如果电脑在O（ld N）胜过O（N）之前就已经耗尽了内存，那么由于更高的内存使用率，你可能永远无法从渐近优势中受益。 - AlexWien

@AlexWien- 我可能对此有所错误，但我相当自信你看到的减速是因为链表必须遍历一半的列表才能找到插入点。换句话说，数组和链表都必须做O(n)的工作：数组用于洗牌，链表用于搜索。我非常怀疑这意味着一个巨大的BST会比一个巨大的数组慢。我的所有实际经验都与你所声称的相矛盾。 - templatetypedef

@templatetypedef 我以前的方法是错误的，保持数组排序不是一个好主意，所以我改为先构建数组，然后对其进行排序，这是最简单和可能最快的方法，如果您可以接受一旦构建就无法更改的不可变结构的限制。 （对于值高达100k的情况，即使对于动态结构，我仍然会使用数组方法，因为它的实现成本更低）：答案已更新 - AlexWien