访问问题：从整数的整数中找到中值

Question

有一个文件包含10G（1000000000）个整数，请查找这些整数的中值。你得到2G内存来做到这一点。任何人都可以想出一个合理的方式？谢谢！

Answer 1

创建一个8字节的数组，其长度为2^16个条目。拿出你的输入数字，移出底部的16位，并创建一个直方图。

现在，您在该直方图中计数，直到达到覆盖值中点的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 
} 

这里是工作的一个小组输入数据：

scala> medianFinder(List(1,123,12345,1234567,123456789)) 
res18: Int = 12345 

如果你有存储64个整数，你可以相反，在4遍中使用相同的策略。

Answer 2

如果文件是文本格式，只需在读入文件时将其转换为整数即可，因为作为字符存储的整数可能比存储为整数的整数需要更多的空间取决于整数的大小和文本文件的类型。编辑：你编辑你的原始问题;现在我可以看到你无法将它们读入内存中，请参阅下文。

如果您无法读取它们到内存中，这就是我想出了：

1. 弄清楚你多少整数有。你可能从一开始就知道这一点。如果不是，那么它只需要通过文件一次。假设这是S.

2. 使用你的2G内存找出x个最大的整数（无论你能容纳多少）。你可以在文件中进行一次传递，在某种排序列表中保留x最大，随着时间的推移丢弃其余的剩余部分。现在你知道第x个最大的整数。除了第x个，我可以称之为x1，你可以放弃所有这些。

3. 再做一遍，找到下一个x最大的整数小于 x1，最小的是x2。

4. 我想你可以看到我要去的地方。经过几次后，您将读取（S/2）中最大的整数（您必须记录您找到的整数数量），这是您的中位数。如果S是偶数，那么你会平均中间的两个。

Answer 3

对文件进行遍历并找到整数和最小和最大整数值的数量。

取最小值和最大值的中点，并获得中点任意一侧的值的最小值和最大值 - 再次读取文件。

分区计数> count =>中位于该分区内。

对分区重复考虑“分区向左”的大小（易于维护），并且还要注意min = max。

我确定这个工作也适用于任意数量的分区。

Answer 4

1. 对文件进行磁盘上external mergesort对整数进行排序（如果尚未知道，则对其进行计数）。
2. 一旦文件被排序，寻找到中间数字（奇数），或平均文件中的两个中间数字（即使是例子）以获得中位数。

使用的内存量是可调整的，不受原始文件中整数数量的影响。外部排序的一个警告是中间排序数据需要写入磁盘。

鉴于n =原始文件整数数量：

• 运行时间：O(nlogn)
• 内存：O(1)，可调
• 盘：O(n)

Answer 5

可以使用Medians of Medians algorithm 。

Answer 6

查看托本的方法在这里：。它也在文档底部的C中实现。

Answer 7

我最好猜测，中位数的概率中位数是最快的。方药：

1. 采取下一组N个整数（N应该是足够大的，说1000或10000元）
2. 然后计算这些整数位，并将其分配给变量X_new。

3. 如果迭代不是第一 - 计算二位数中位数：

   X_global =（X_global + X_new）/ 2

4. 当你将看到X_global波动并不多 - 这意味着你发现数据的大致中位数。

但也有一些注意事项：

• 问题出现了 - 是中间误差可以接受。
• 整数随机必须以统一的方式进行分配，对于解决工作

编辑： 我打了一下这个算法，改变了一点想法 - 在每次迭代中，我们应该总结X_new随体重，如：从[0.5 .. 1]

k，以及增加在每次迭代：

X_global = K * X_global +（1-K）* X_new。

要点是使中值的计算在极少量的迭代中快速收敛到某个数。因此，只有252次迭代才能在100000000个阵列元素之间找到非常接近的中值（具有大误差）！检查该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; 

} 

哎呀好像我说的是平均数，中位数没有。如果是这样，你需要正确的中位数，而不是指 - 忽略我的帖子。无论如何，平均数和中位数都是非常相关的概念。

祝你好运。

Answer 8

这是由@Rex Kerr描述的算法，用Java实现。

/** 
* 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; 
} 

一些测试用例和算法的更新可以找到here。