algorithm - 在无序列表的多个子范围内查找中位数

Question

例如给定一个包含 N 个元素的无序列表，找到子范围 0..100、25..200、400..1000、10..500 的中位数，...我认为没有比遍历每个子范围并运行标准中值查找算法更好的方法了。

一个简单的例子:[5 3 6 2 4]0..3 的中位数是 5 。 (不是 4，因为我们要的是原始列表前三个元素的中位数)

Answer 1

整数元素:

如果您的元素类型是整数，那么最好的方法是为位于您的任何子范围内的每个数字设置一个桶，其中每个桶用于计算在您的输入元素中找到的相关整数的数字(例如，bucket[100] 存储输入序列中有多少个 100)。基本上可以通过以下步骤实现:

1. 为位于您的任何子范围内的每个数字创建存储桶。
2. 遍历所有元素，对于每个数字 n，如果我们有 bucket[n]，则 bucket[n]++。
3. 根据存储在您的存储桶中的聚合值计算中位数。

换句话说，假设您有一个子范围 [0, 10]，并且您想要计算中位数。桶方法基本上计算输入中有多少 0，输入中有多少 1，等等。假设有n个数在[0, 10]范围内，那么中位数就是第n/2最大的元素，可以是通过找到 i 来识别 bucket[0] + bucket[1] ... + bucket[i] 大于或等于 n/2 但 bucket[0] + ... + bucket[i - 1] 小于 n/2。

这样做的好处是，即使您的输入元素存储在多台机器上(即分布式案例)，每台机器都可以维护自己的存储桶，并且只需要聚合值即可通过 Intranet。

您还可以使用分层桶，它涉及多个 channel 。在每次传递中，bucket[i] 计算输入中特定范围内的元素数量(例如，[i * 2^K, (i+1) * 2^ K])，然后通过识别每一步之后介质位于哪个桶来缩小问题空间，然后在下一步中将K减少1 , 并重复直到您可以正确识别介质。

---

浮点元素

整个元素可以放入内存:

如果您的整个元素都可以放入内存中，那么最好先对 N 个元素进行排序，然后找到每个子范围的中位数。 The linear time heap solution如果您的子范围数量小于 logN，在这种情况下也能很好地工作。

整个元素无法放入内存，而是存储在一台机器上:

通常，一个 external sort通常需要三个磁盘扫描。因此，如果你的子区间数大于或等于 3，那么先对 N 个元素进行排序，然后只从磁盘加载必要的元素来找到每个子区间的中位数是最好的选择。否则，简单地对每个子范围执行扫描并选取子范围中的那些元素会更好。

整个元素存储在多台机器上:由于求中值是一个整体算子，不能根据输入的几个部分的中值推导出整个输入的最终中值，所以无法用几句话描述它的解决方案是一个难题，但有研究(见this 作为例子)一直关注这个问题。