采访问题：从整数倍中找出中位数
有一个包含10G（1000000000）个整数的文件，请查找这些整数的中值。 你给2G内存来做到这一点。 任何人都可以想出一个合理的方法？ 谢谢！
创build一个包含2 ^ 16个条目的8字节长度的数组。 拿你的input数字，移出底部的16位，并创build一个直方图。
现在，直到你到达包含值的中点的bin为止。
再次通过，忽略所有没有相同的最高位集合的数字，并制作底部位的直方图。
通过该直方图进行计数，直到到达覆盖（整个列表）值中点的bin。
现在你知道中位数，在O(n)时间和O(1)空间（实际上在1 MB以下）。
这里有一些示例Scala代码，这样做：
def medianFinder(numbers: Iterable[Int]) = { def midArgMid(a: Array[Long], mid: Long) = { val cuml = a.scanLeft(0L)(_ + _).drop(1) cuml.zipWithIndex.dropWhile(_._1 < mid).head } val topHistogram = new Array[Long](65536) var count = 0L numbers.foreach(number => { count += 1 topHistogram(number>>>16) += 1 }) val (topCount,topIndex) = midArgMid(topHistogram, (count+1)/2) val botHistogram = new Array[Long](65536) numbers.foreach(number => { if ((number>>>16) == topIndex) botHistogram(number & 0xFFFF) += 1 }) val (botCount,botIndex) = midArgMid(botHistogram, (count+1)/2 - (topCount-topHistogram(topIndex))) (topIndex<<16) + botIndex }
这里正在处理一小组input数据：
scala> medianFinder(List(1,123,12345,1234567,123456789)) res18: Int = 12345
如果你有64位整数存储，你可以使用相同的策略，而不是4遍。
你可以使用Medians的Mediansalgorithm 。
如果文件是文本格式的，你可能可以把它放在内存中，只要把它们转换成整数就可以了，因为存储为字符的整数可能比整数存储的整数占用更多的空间，这取决于整数的大小和文本文件的types。 编辑：你编辑你的原始问题; 我现在可以看到，你不能将它们读入内存，见下文。
如果你不能把它们读入记忆中，那就是我想到的：
-
找出你有多less个整数。 你可能从一开始就知道这一点。 如果不是，那么只需要通过一个文件。 比方说这是S.
-
使用你的2G内存findx最大的整数（不pipe你可以适合多less）。 你可以在文件中进行一次传递，在某种sorting的列表中保留最大的x，随着时间的推移丢弃其余的。 现在你知道第x个最大的整数。 你可以放弃所有这些，除了第x个，我将称之为x1。
-
再做一遍，find下一个x最大的小于 x1的整数，最小的是x2。
-
我想你可以看到我要去哪里。 经过几次之后，您将读取（S / 2）最大的整数（您将必须跟踪您find的整数），这是您的中位数。 如果S是平均，那么你会平均中间的两个。
对文件进行遍历，find整数和最小和最大整数值。
取最小值和最大值的中点，并在中点的任何一侧获得数值，最小值和最大值 – 再次读取文件。
分区计数>计数=>中位数在该分区内。
重复的分区，考虑到“分区左”的大小（易于维护），也看最小=最大。
肯定这个也适用于任意数量的分区。
- 对文件进行磁盘上的外部合并sorting来对整数进行sorting（如果不是已知的，则对其进行计数）。
- 一旦文件被sorting，寻find中间数字（奇数），或者平均文件中的两个中间数字（偶数情况）来获得中位数。
使用的内存量是可调整的，不受原始文件中整数的影响。 外部sorting的一个警告是中间sorting数据需要写入磁盘。
给定n =原始文件中的整数数量：
- 运行时间：
O(nlogn) - 内存：
O(1)，可调 - 磁盘：
O(n)
在这里查看Torben的方法： http : //ndevilla.free.fr/median/median/index.html 。 它也在文档底部的C中实现。
我最好的猜测是，中位数的概率中位数是最快的。 食谱：
- 取下一组N个整数（N应该足够大，说1000或10000个元素）
- 然后计算这些整数的中位数，并将其分配给variablesX_new。
-
如果迭代不是首先计算两个中位数的中位数：
X_global =（X_global + X_new）/ 2
-
当你看到X_global波动不大 – 这意味着你find了大概的数据中位数。
但是有一些说明：
- 问题出现 – 中位数错误是否可以接受。
- 整数必须以统一的方式随机分配，以便解决工作
编辑：我已经玩了一下这个algorithm，改变了一些想法 – 在每次迭代中，我们应该减less重量X_new，如：
X_global = k * X_global +（1.-k）* X_new：
k从[0.5..1]开始，并在每次迭代中增加。
要点是要使中值的计算在很小的迭代次数内快速收敛到某个数。 因此， 在252次迭代中，在100000000个数组元素之间find非常接近的中值（具有大的误差） ！ 检查这个C实验：
#include <stdlib.h> #include <stdio.h> #include <time.h> #define ARRAY_SIZE 100000000 #define RANGE_SIZE 1000 // probabilistic median of medians method // should print 5000 as data average // from ARRAY_SIZE of elements int main (int argc, const char * argv[]) { int iter = 0; int X_global = 0; int X_new = 0; int i = 0; float dk = 0.002; float k = 0.5; srand(time(NULL)); while (i<ARRAY_SIZE && k!=1.) { X_new=0; for (int j=i; j<i+RANGE_SIZE; j++) { X_new+=rand()%10000 + 1; } X_new/=RANGE_SIZE; if (iter>0) { k += dk; k = (k>1.)? 1.:k; X_global = k*X_global+(1.-k)*X_new; } else { X_global = X_new; } i+=RANGE_SIZE+1; iter++; printf("iter %d, median = %d \n",iter,X_global); } return 0; }
奥普斯似乎在谈论平均数，而不是中位数。 如果是这样，你需要正确的中位数，而不是意味着 – 忽略我的post。 无论如何，平均数和中位数是非常相关的概念。
祝你好运。
这里是由Java中实现的@Rex Kerr描述的algorithm。
/** * Computes the median. * @param arr Array of strings, each element represents a distinct binary number and has the same number of bits (padded with leading zeroes if necessary) * @return the median (number of rank ceil((m+1)/2) ) of the array as a string */ static String computeMedian(String[] arr) { // rank of the median element int m = (int) Math.ceil((arr.length+1)/2.0); String bitMask = ""; int zeroBin = 0; while (bitMask.length() < arr[0].length()) { // puts elements which conform to the bitMask into one of two buckets for (String curr : arr) { if (curr.startsWith(bitMask)) if (curr.charAt(bitMask.length()) == '0') zeroBin++; } // decides in which bucket the median is located if (zeroBin >= m) bitMask = bitMask.concat("0"); else { m -= zeroBin; bitMask = bitMask.concat("1"); } zeroBin = 0; } return bitMask; }
一些testing用例和algorithm的更新可以在这里find。
