finden einen Median von N^2 Nummern Speicher für N von ihnen mit

Question

Ich habe versucht, über verteiltes Rechnen zu lernen und kam über ein Problem Median einer großen Menge von Zahlen zu finden:

Nehmen wir an, wir haben eine große Menge von Zahlen (sagen wir mal, die Anzahl der Elemente ist N * K), die nicht in den Speicher passen (Größe N). Wie finden wir den Median dieser Daten? Angenommen, die an dem Speicher durchgeführten Operationen sind unabhängig, d. H. Wir können in Betracht ziehen, dass es K Maschinen gibt, die jeweils höchstens N Elemente verarbeiten können.

Ich dachte, dass Median der Mediane für diesen Zweck verwendet werden kann. Wir können N Zahlen auf einmal in den Speicher laden. Wir finden den Median der in O(logN) gesetzten Zeit und speichern ihn.

Dann speichern wir alle diese K-Medien und finden den Median der Mediane. Auch hier O(logK), bisher war die Komplexität O(K*logN + logK).

Aber dieser Median Median ist nur ein ungefährer Median. Ich denke, es wird optimal sein, es als Drehpunkt zu verwenden, um eine Best-Case-Leistung zu erzielen, aber dafür müssen wir alle N * K-Nummern in den Speicher passen.

Wie können wir den tatsächlichen Median des Satzes jetzt finden, dass wir einen guten ungefähren Drehpunkt haben?

Answer 1

Warum erstellen Sie kein Histogramm? I.e. die Anzahl der Fälle (Werte), die in jede der verschiedenen Kategorien fallen. Die Kategorien sollten aufeinanderfolgende, nicht überlappende Intervalle einer Variablen sein.

Mit diesem Histogramm können Sie eine erste Schätzung des Medians vornehmen (d. H. Median liegt zwischen [a, b]) und wissen, wie viele Werte in dieses Intervall (H) fallen. Wenn H < = N ist, lesen Sie die Nummern erneut, ignorieren Sie diese außerhalb dieses Intervalls und verschieben Sie die Nummern innerhalb des Intervalls nach RAM. Finde den Median.

Wenn H> N, machen Sie eine neue Partition des Intervalls und wiederholen Sie den Vorgang. Es sollte nicht mehr als 2 oder 3 Iterationen dauern.

Beachten Sie, dass Sie für jede Partition nur a, b, ein Delta und das Array mit der Anzahl der Werte, die in jedes Subintervall fallen, speichern müssen.

BEARBEITEN. Es wird etwas komplizierter, als ich erwartet habe. In jeder Iteration nach der Schätzung des Intervalls, in das der Median fällt, sollten wir auch berücksichtigen, "wie viel" Histogramm wir rechts und links von diesem Intervall verlassen. Ich habe auch die Stop-Bedingung geändert. Wie auch immer, ich habe eine C++ Implementierung gemacht.

#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; 
} 

Ich habe auch eine naive Berechnung des Median (Sortierung) enthalten, um mit den Ergebnissen des Algorithmus zu vergleichen.4 oder 5 Iterationen sind genug. Es bedeutet, dass wir das Set nur 4-5 mal vom Netzwerk oder HDD lesen müssen.

Einige Ergebnisse:

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) 

Wenn Sie den Algorithmus parallelisieren wollen, kann jede Maschine N Elemente haben und das Histogramm zu berechnen. Sobald es berechnet wurde, würden sie es an die Mastermaschine senden, die alle Histogramme summieren würde (einfach, es kann sehr klein sein ... der Algorithmus arbeitet sogar mit Histogrammen von 2 Intervallen). Dann würde es neue Befehle (d. H. Das neue Intervall) an die Slave-Maschinen senden, um neue Histogramme zu berechnen. Beachten Sie, dass jede Maschine keine Kenntnisse über die N Elemente der anderen Maschinen haben muss.

Answer 2

Wenn Sie davon ausgehen, dass Ihre Zahlen sind B Bit-Integer (Floating Point ist zu fein, weil Sie auf Zeichen basierend sortieren und dann basierend auf den Exponenten und dann basierend auf der Mantisse), dann können Sie das Problem in O(N^2 B/K) Zeit lösen wenn Sie K Prozessoren und N^2 Nummern haben. Sie tun im Grunde Binärsuche: Beginnen Sie mit einem Drehpunkt gleich der Mitte des Bereichs, und verwenden Sie Ihre K Prozessoren, um zu zählen, wie viele Zahlen kleiner als und gleich und größer als der Drehpunkt sind. Dann wissen Sie, ob der Median gleich dem Drehpunkt oder größer oder kleiner als der Drehpunkt ist. Weiter mit der binären Suche. Jeder binäre Suchschritt benötigt O(N^2 /K) Zeit, um durch die Liste der Nummern zu gehen, was O(N^2 B/K) Gesamtlaufzeit gibt.

Answer 3

Nehmen Sie eine Stichprobe von N von ihnen. Mit konstanter Wahrscheinlichkeit, die von c abhängt, liegt der Median dieser Stichprobe innerhalb von c * N Stellen des Medians. Wenn Sie dies zweimal tun, haben Sie die möglichen Positionen des Medians mit konstanter Wahrscheinlichkeit auf linear viele reduziert. Tun Sie, was für eine schreckliche Sache Sie möchten, um das Element des entsprechenden Ranges auszuwählen.