查找有他們的N個存儲N^2號的位數

Question

我是想了解分佈式計算和跨找到一個大組數字的中位數的問題就來了：

假設我們有一大堆數字（可以說元素數量是N * K）不能放入內存（大小爲N）。我們如何找到這些數據的中位數？假設在存儲器上執行的操作是獨立的，即我們可以認爲有K個機器每個最多可處理N個元素。

我認爲中位數的中位數可以用於此目的。 我們可以一次將N個數字加載到內存中。我們找到O(logN)時間的中間值並保存。

然後我們保存所有這些K中位數，並找出中位數的中位數。再次O(logK)，到目前爲止的複雜性一直是O(K*logN + logK)。

但這個中位數的中位數只是一個近似的中位數。我認爲使用它作爲獲得最佳性能表現的關鍵是最理想的，但爲此我們需要將所有N * K數字都放在內存中。

我們現在可以如何找到該組的實際中位數，我們有一個很好的近似關鍵點？

Answer 1

爲什麼不建立直方圖？即屬於幾個類別的情況（值）的數量。類別應該是連續的，不重疊的變量區間。使用此直方圖可以對中間值進行首次估計（即中值在[a，b]之間），並知道有多少值落入該區間（H）。如果H < = N，請再次讀取數字，忽略超出此間隔的數字，並將間隔內的數字移至RAM。找到中位數。

如果H> N，做一個新的間隔分區並重復該過程。它不應該超過2或3次迭代。

請注意，對於每個分區，只需存儲a，b，一個Delta和具有落入每個子區間的值數量的數組。

編輯。它預計會變得更加複雜一些。在估計間隔中間值後的每次迭代中，我們還應該考慮在這個間隔的右側和左側留下「多少」直方圖。我也改變了停止條件。無論如何，我做了一個C++實現。

#include <iostream> 
#include <algorithm> 
#include <time.h> 
#include <stdlib.h> 

//This is N^2... or just the number of values in your array, 
//note that we never modify it except at the end (just for sorting 
//and testing purposes). 
#define N2 1000000 
//Number of elements in the histogram. Must be >2 
#define HISTN 1000 

double findmedian (double *values, double min, double max); 
int getindex (int *hist); 
void put (int *hist, double min, double max, double val, double delta); 


int main() 
{ 
    //Set max and min to the max/min values your array variables can hold, 
    //calculate it, or maybe we know that they are bounded 
    double max=1000.0; 
    double min=0.0; 
    double delta; 
    double values[N2]; 
    int hist[HISTN]; 
    int ind; 
    double median; 
    int iter=0; 
    //Initialize with random values 
    srand ((unsigned) (time(0))); 
    for (int i=0; i<N2; ++i) 
     values[i]=((double)rand()/(double)RAND_MAX); 

    double imin=min; 
    double imax=max; 

    clock_t begin=clock(); 
    while (1) { 
     iter++; 
     for (int i=0; i<HISTN; ++i) 
      hist[i]=0; 

     delta=(imax-imin)/HISTN; 
     for (int j=0; j<N2; ++j) 
      put (hist, imin, imax, values[j], delta); 

     ind=getindex (hist); 
     imax=imin; 
     imin=imin+delta*ind; 
     imax=imax+delta*(ind+1); 

     if (hist[ind]==1 || imax-imin<=DBL_MIN) { 
      median=findmedian (values, imin, imax); 
      break; 
     } 
    } 

    clock_t end=clock(); 
    std::cout << "Median with our algorithm: " << median << " - " << iter << "iterations of the algorithm" << std::endl; 
    double time=(double)(end-begin)/CLOCKS_PER_SEC; 
    std::cout << "Time: " << time << std::endl; 

    //Let's compare our result with the median calculated after sorting the 
    //array 
    //Should be values[(int)N2/2] if N2 is odd 
    begin=clock(); 
    std::sort (values, values+N2); 
    std::cout << "Median after sorting: " << values[(int)N2/2-1] << std::endl; 
    end=clock(); 
    time=(double)(end-begin)/CLOCKS_PER_SEC; 
    std::cout << "Time: " << time << std::endl; 

    return 0; 
} 

double findmedian (double *values, double min, double max) { 
    for (int i=0; i<N2; ++i) 
     if (values[i]>=min && values[i]<=max) 
      return values[i]; 

    return 0; 
} 

int getindex (int *hist) 
{ 
    static int pd=0; 
    int left=0; 
    int right=0; 
    int i; 

    for (int k=0; k<HISTN; k++) 
     right+=hist[k]; 

    for (i=0; i<HISTN; i++) { 
     right-=hist[i]; 
     if (i>0) 
      left+=hist[i-1]; 
     if (hist[i]>0) { 
      if (pd+right-left<=hist[i]) { 
       pd=pd+right-left; 
       break; 
      } 
     } 

    } 

    return i; 
} 

void put (int *hist, double min, double max, double val, double delta) 
{ 
    int pos; 
    if (val<min || val>max) 
     return; 

    pos=(val-min)/delta; 
    hist[pos]++; 
    return; 
} 

我還包括一個天真的計算中位數（排序），以便與算法的結果進行比較。4或5次迭代就足夠了。這意味着我們只需要從網絡或硬盤讀取設置4-5次。

的一些結果：

N2=10000 
HISTN=100 

Median with our algorithm: 0.497143 - 4 iterations of the algorithm 
Time: 0.000787 
Median after sorting: 0.497143 
Time: 0.001626 

(Algorithm is 2 times faster) 

N2=1000000 
HISTN=1000 

Median with our algorithm: 0.500665 - 4 iterations of the algorithm 
Time: 0.028874 
Median after sorting: 0.500665 
Time: 0.097498 

(Algorithm is ~3 times faster) 

如果要並行算法，每臺機器可以有N個元素，並計算直方圖。一旦計算出來，他們就會將它發送給主機器，這將對所有的直方圖進行求和（容易，它可以非常小...算法甚至可以在2個間隔的直方圖上運行）。然後它會發送新的指令（即新的時間間隔）給從機，以便計算新的直方圖。請注意，每臺機器不需要了解其他機器擁有的N個元素。

Answer 2

如果你認爲你的號碼是B位二進制整數（浮點數是沒關係，因爲你可以排序基於標誌，然後根據該指數，然後根據尾數），那麼您可以在O(N^2 B/K)時間解決問題如果您有K處理器和N^2號碼。您基本上執行二分搜索：從等於該範圍中間的樞軸開始，並使用您的K處理器來計算有多少個數小於等於並大於該數據透視。然後你就會知道中位數是否等於樞軸位，或者大於或小於樞軸位。繼續進行二分查找。每個二進制搜索步驟需要O(N^2 /K)時間才能遍歷數字列表，給出O(N^2 B/K)整體運行時間。

Answer 3

取其中的N個隨機樣本。在恆定的概率依賴於c的情況下，該隨機樣本的中值位於中值的c * N個位置內。如果你這樣做了兩次，那麼以不變的概率，你將中位數的可能位置縮小到線性許多。做你喜歡的任何可怕的事情來選擇適當等級的元素。