题 有效百分位数查找的数据结构?


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

  • ,它为集合添加了一个新的键/值对,
  • 删除,从集合中删除键/值对,
  • 百分,它告诉与给定密钥相关的值在哪个百分位,和
  • 推荐给百分,它接受百分位数并返回其值为至少给定百分位数的最低值的键。

例如,该数据结构可以用于在接收全国范围的测试分数流时有效地确定给定学生的百分位数,或者识别具有异常好或坏的服务质量的医院。

有没有办法让这些操作有效运行(比如,次线性时间?)


11
2017-12-21 22:20


起源


如果你想查找 相同 每次百分位数,你可以保持一对堆高于/低于所需百分位数的值。看到 stackoverflow.com/questions/3738349/... - Peter Cordes


答案:


实现此数据结构的一种可能方式是使用a的混合 订单统计树 和a 哈希表

订单统计树是一种平衡二叉搜索树,除了正常的二叉搜索树操作外,还支持另外两个操作:

  • (键),返回树中元素的数量小于给定元素,和
  • 选择(k),返回树中第k个最小元素。

可以通过扩充正常的平衡二叉搜索树(例如,a。)来构建订单统计树 红/黑树 或者 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. 我们将存储一个二级哈希表,用于将键映射到它们的关联值。

这两项更改使我们可以为数据结构实现所需的功能。为了使数据结构按键进行百分位查找,我们首先使用给定键查询哈希表以查找其关联值。然后,我们对值进行百分位查找,如前所述。为了使数据结构告诉我们一个值为第一个等于或高于给定百分位数的密钥,我们在订单统计树上执行正常的查找百分位操作,如上所述,然后查找与给定值相关联的密钥。

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

  • :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)。
  • 查找百分:O(1)将百分位数映射到排名所需的时间,以及执行该操作所需的O(log n)时间 选择 操作。总时间是O(log n)最坏情况。

希望这可以帮助!


10
2017-12-21 22:20





有一种简单而高效的可能性:

如果你只能在最终填满的学生结构中搜索百分位数,那么:

当您不知道元素的数量时,使用ArrayList动态构建。
如果你知道它们,那么直接从数组开始,否则从动态数组创建数组。 (例如java中的ArrayList)。

:不是必要的,取而代之的是在最后添加,并排序一次。
删除:不是必要的,如果你可以忍受。
告诉百分:更简单:非常接近的东西:element [length * percentile]:O(1)

在实践中,阵列方法将比平衡树方法快得多,至少在java中, 当你的应用程序可以建立一次数组(例如每日学生评估,每天建立它)

我已经使用自编写的ArrayListInt实现了上面的(my)算法,它与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的排序数组只能通过哈希表来打败

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


2
2017-12-21 22:52



-1:Yikes - 似乎你可能从根本上误解了复杂性分析。一个事实 O(N) 方法可能比一个更快 O(log(N)) 特定(小)值的方法 N  才不是 意思是 O(N) 方法是 总是 更好,正如你所说的那样。 Big O分析的重点是渐近性能 - 如 N 倾向于更大的价值 O(log(N)) 方法将赢得胜利 O(N),不论恒定/低阶因素。 - Darren Engwirda
你真的确定memcopy可以比10000元素树的BST查找更快地移动10000个元素吗?随着现代内存分配器优化局部性,我非常怀疑这是真的。你可以用一些数据或参考来支持吗? - templatetypedef
@Yikes:我写道:在实践中总是赢,这意味着真正的应用程序,而不是你提供MAX_INT元素的基准。进一步不要忘记内存使用,如果计算机在O(ld N)胜过O(N)之前耗尽内存,那么你可能处于O(ld N)由于更高的memeroy usgae永远不会受益的情况从它的渐近优势。 - AlexWien
@ AlexWien-我可能错了,但我相信你看到的减速是因为链表必须遍历列表的一半才能找到插入点。换句话说,数组和链表都必须执行O(n)工作:用于混洗的数组和用于搜索的列表。我严重怀疑这是否意味着巨大的BST将比一个巨大的阵列慢。我所有的实践经验都与你所声称的相矛盾。 - templatetypedef
@templatetypedef我的旧方法是错误的,保持数组排序不是一个好主意,所以我改为构建数组并对其进行排序一次,这是最容易和最快的,如果你忍受不可变结构的限制一旦建立。 (对于高达100k的值,我仍然会使用数组方法,即使是动态结构,因为它的实现更便宜):答案更新 - AlexWien