6

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

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

4

4 回答 4

2

整数元素：

如果您的元素的类型是整数，那么最好的方法是让每个数字的存储桶位于您的任何子范围内，其中每个存储桶用于计算在您的输入元素中找到的与其关联的整数的数字（例如,存储输入序列中有bucket[100]多少个 s）。100基本上你可以通过以下步骤来实现它：

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

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

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

您还可以使用分层存储桶，它涉及多次传递。在每一次通过中，bucket[i]计算输入中位于特定范围内的元素数量（例如[i * 2^K, (i+1) * 2^K]，并重复，直到您可以正确识别介质。K1

浮点元素

整个元素可以放入内存：

如果您的整个元素都可以放入内存，那么首先对 N 个元素进行排序，然后找到每个子范围的中位数是最佳选择。 如果您的子范围的数量小于logN.

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

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

整个元素存储在多台机器中： 由于求中位数是一个整体算子，也就是说你不能根据输入的几个部分的中位数推导出整个输入的最终中位数，所以很难描述它的解决方案。几句话，但有研究（以this为例）一直专注于这个问题。

于 2013-08-12T06:14:10.717 回答
0

我认为随着子范围数量的增加，您会很快发现排序然后检索所需的元素编号会更快。

在实践中，因为您可以调用高度优化的排序例程。

在理论上，也许在实践中也是如此，因为因为您正在处理整数，所以您不需要为排序支付 n log n - 请参阅http://en.wikipedia.org/wiki/Integer_sorting。

如果您的数据实际上是浮点数而不是 NaN，那么一点点旋转实际上将允许您对它们使用整数排序 - 来自 - http://en.wikipedia.org/wiki/IEEE_754-1985#Comparing_floating-point_numbers -二进制表示具有特殊属性，除了 NaN，任何两个数字都可以像符号和幅度整数一样进行比较（尽管对于现代计算机处理器，这不再直接适用）：如果符号位不同，则负数在正数之前number （除了负零和正零应该被认为是相等的），否则，相对顺序与字典顺序相同，但对于两个负数相反；字节顺序问题适用。

因此，您可以检查 NaN 和其他有趣的东西，假设浮点数是符号 + 幅度整数，在负数时减去以纠正负数的排序，然后将其视为正常的 2s 补码有符号整数，排序，然后反转该过程。

于 2013-08-12T05:01:46.837 回答
0

答案最终将是“取决于”。有多种方法，其中任何一种都可能适用于您可能遇到的大多数情况。问题是每个人都会针对不同的输入执行不同的操作。一个人可能对一类输入表现更好，而另一个对另一类输入表现更好。

例如，当您必须测试的范围数大于 log(N) 时，排序然后对范围的极值执行二进制搜索然后直接计算中位数的方法将很有用。另一方面，如果范围的数量小于 log(N)，最好将给定范围的元素移动到数组的开头并使用线性时间选择算法来找到中值。

所有这一切都归结为分析以避免过早的优化。如果您实施的方法被证明不是系统性能的瓶颈，那么与简化程序中的瓶颈部分相比，弄清楚如何改进它不会是一个有用的练习。

于 2013-08-12T20:09:55.053 回答
0

我的想法：

  • 将列表排序为数组（使用任何适当的排序算法）

  • 对于每个范围，使用二进制搜索查找范围开始和结束的索引

  • 通过简单地添加它们的索引并除以 2 来找到中值（即范围的中值[x,y]是arr[(x+y)/2]）

预处理时间：通用排序算法（如快速排序）的 O(n log n) 或所选排序例程的运行时间

每次查询的时间：O(log n)

动态列表：

以上假设列表是静态的。如果可以在查询之间自由添加或删除元素，则可以使用修改后的二叉搜索树，每个节点都会记录其拥有的后代数量。这将允许与上述动态列表相同的运行时间。

于 2013-08-12T09:22:17.273 回答