訪問問題：從整數的整數中找到中值

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。