それらのN

Question

ためのメモリを備えたN^2つの数字の中央値を検索し、私は、分散コンピューティングについて学ぶしようと数字の大規模なセットの中央値を見つける問題に出くわした：

は、我々が持っていると仮定メモリ（サイズN）に収まらない大きな数の集合（要素の数をN * Kといいます）。このデータの中央値はどのようにして求められますか？メモリ上で実行される演算が独立していると仮定すると、すなわち、N個の要素を処理できるK個の機械がそれぞれあると考えることができる。

私は中央値の中央値がこの目的のために使用できると考えました。 N個の数値を一度にメモリにロードすることができます。そのセットの中央値はO(logN)になり、保存します。

これらのK medianをすべて保存し、中央値の中央値を調べます。再度O(logK)、これまで複雑さはO(K*logN + logK)でした。

しかし、この中央値の中央値はちょうどおおよその中央値です。最良のケースパフォーマンスを得るためにはピボットとして使うのが最適だと思いますが、そのためにはすべてのN * K数をメモリに収める必要があります。

私たちは現在、私たちは良い近似ピボットを持っているので、セットの実際の中央値をどのように見つけることができますか？

Answer 1

なぜヒストグラムを作成しないのですか？私。いくつかのカテゴリのそれぞれに該当するケース（値）の数。カテゴリは、変数の連続したオーバーラップしない間隔である必要があります。

このヒストグラムを使用すると、中央値の最初の推定値（[中央値は[a、b]の間にあります）と、この間隔（H）に入る値の数を知ることができます。 H < = Nの場合は、この間隔以外でこれらを無視して数字をもう一度読み、その間隔内の数字をRAMに移動します。中央値を求める。

H> Nの場合、間隔の新しいパーティションを作成し、手順を繰り返します。 2回または3回以上の繰り返しは必要ありません。

各パーティションに対して、a、b、デルタ、および各サブインターバルに入る値の数を格納するだけでよいことに注意してください。

EDIT。それは私が期待していたもう少し複雑なものになっていった。中央値が入る間隔を見積もった後の各反復で、この間隔の右側と左側に「いくら」のヒストグラムを残すかを考慮する必要があります。私は停止条件も変えました。とにかく、私は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回の反復で十分です。つまり、ネットワークまたはHDDからセットを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ビットの2進整数（浮動小数点は符号に基づいてソートしてから指数に基づいてソートしてから仮数部に基づいてソートすることができるため）であると仮定すると、O(N^2 B/K)時間で問題を解決できますKプロセッサーとN^2プロセッサーの場合。あなたは基本的にバイナリ検索を行います：範囲の中央に等しいピボットから始め、Kプロセッサを使用してピボットよりも小さいか等しいピリオドの数を数えます。次に、中央値がピボットと等しいかピボットよりも大きいか小さいかがわかります。バイナリ検索を続行します。それぞれのバイナリ検索ステップでは、の合計実行時間が与えられ、数字のリストを調べる時間はO(N^2 /K)になります。

Answer 3

N個のランダムサンプルを取ってください。 cに依存する一定の確率で、このランダムサンプルの中央値は中央値のc * Nの範囲内にある。これを2回実行すると、一定の確率で中央値の可能な位置を線形に多く絞ります。適切なランクの要素を選択するのが好きな恐ろしいことをしてください。