14

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

  • Insert，向集合中添加一个新的键/值对，
  • Delete，从集合中删除一个键/值对，
  • Percentile，它告诉与给定键关联的值在哪个百分位，以及
  • Tell- Percentile ，它接受一个百分位数并返回其值为至少给定百分位数的最小值的键。

例如，可以使用这种数据结构来有效地确定给定学生在接收全国测试分数流时所处的百分位数，或者识别服务质量异常好或差的医院。

有没有办法让这些操作有效地运行（比如，亚线性时间？）

4

2 回答 2

14

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

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

  • Rank（键），返回树中小于给定元素的元素数量，以及
  • Select (k)，它返回树中第 k 个最小的元素。

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

现在，让我们假设您纯粹存储值分数，而不是关键/百分比分数。在这种情况下，如下实现百分位查找将非常简单。将所有值存储在订单统计树中。要确定给定值的百分位分数，请使用顺序统计树上的排名操作来查找该值出现在哪个索引处。这给出了一个数字，范围从 0 到 n - 1（其中 n 是树中元素的数量），表示该分数在顺序统计树中的位置。然后，您可以将该数字乘以 99 / (n - 1)，以根据需要获得在 0 到 99 范围内运行的值的百分位数。

要确定大于某个百分位的最小值，可以使用如下选择操作。给定一个介于 0 和 99 之间的百分位数，将该百分位数乘以 99 / (n - 1) 得到一个介于 0 和 n - 1 之间的实数，包括 0 和 n - 1。取该数的上限会产生 0 到 n - 1 范围内的自然数，包括 0 到 n - 1。然后可以使用顺序统计树上的选择操作来查找范围内等于或高于给定百分位数的第一个值。

然而，这些操作假设我们在数据结构中有纯粹的值，而不是键/值对。为了使这个操作适用于键/值对，我们将扩充我们的数据结构如下：

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

这两个变化使得为我们的数据结构实现所需的功能成为可能。为了让数据结构通过键进行百分位查找，我们首先使用给定的键查询哈希表以查找其关联值。然后，我们像以前一样对值进行百分位查找。为了让数据结构告诉我们一个键的值是第一个或高于给定百分位数的键，我们如上所述在顺序统计树上执行正常的 find-percentile 操作，然后查找与给定值关联的键。

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

  • 插入：将值/键对插入订单统计树的 O(log n) 时间，加上将键/值对插入哈希表的 O(1) 分摊时间。总时间为 O(log n) 摊销。
  • 删除：从订单统计树中删除值/键对的 O(log n) 时间，加上 (1) 从哈希表中删除键/值对的摊销时间。总时间为 O(log n) 摊销。
  • 百分位数：O(1) 预期时间来查找与键关联的值，O(log n) 时间来执行排名操作，以及 O(1) 额外时间来将排名映射到百分位数。预计总时间为 O(log n)。
  • Find- Percentile ：将百分位数映射到排名所需的 O(1) 时间，以及执行选择操作所需的 O(log n) 时间。总时间是 O(log n) 最坏情况。

希望这可以帮助！

于 2012-12-21T22:20:24.323 回答
2

有一个简单而高效的可能性：

如果您只能在最终填满的学生结构中搜索百分位数，那么：

当您不知道元素的数量时，使用 ArrayList 动态构建。
如果您知道它们，则直接从数组开始，否则从动态数组创建数组。（例如java中的ArrayList）。

插入：不需要，替换为在末尾添加，并排序一次。
删除：没有必要，如果你能忍受的话。
告诉百分位数：更简单：非常接近：元素[长度*百分位数]：O（1）

在实践中，数组方法将比平衡树方法快得多，至少在 java 中，当您的应用程序可以构建一次数组时（例如每日学生评估，每天构建它）

我已经使用自写的 ArrayListInt 实现了（我的）上述算法，它与 ArrayList 相同，但使用原始类型（double、int）而不是对象类型。当所有数据都被读取后，我对其进行了一次排序。

此外，您还需要键值：
我只需添加一个树图（平衡树）。现在有点怀疑 TreeMap 和附加的百分位数数组是否有意义：这取决于您必须搜索的频率，以及内存使用量与搜索时间的关系。

更新：

结果：treeset vs sorted array（动态构建数组，然后最后排序一次：

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

这个数量的元素（1e7）现在接近限制（1GB 堆空间），在下一步中内存将耗尽（已经发生在 1e7，但是在树集之后清理内存，测量 1e7 的运行也有效。

缺少的是搜索时间，但是带有 binsearch 的排序数组只能被哈希表击败

最后： 如果您可以建立学生集一次，例如每天，那么使用数组方法可以提供更简单的百分位搜索。

于 2012-12-21T22:52:40.217 回答