Berechnen Sie den Median einer Milliarde Zahlen

127

Wenn Sie eine Milliarde Zahlen und einhundert Computer haben, wie können Sie den Median dieser Zahlen am besten ermitteln?

Eine Lösung, die ich habe, ist:

  • Teilen Sie das Set gleichmäßig auf die Computer auf.
  • Sortieren Sie sie.
  • Finden Sie die Mediane für jeden Satz.
  • Sortieren Sie die Sätze nach Medianen.
  • Führen Sie zwei Sätze gleichzeitig vom niedrigsten zum höchsten Median zusammen.

Wenn wir m1 < m2 < m3 ...dann zuerst zusammenführen Set1und Set2und in der resultierenden Menge können wir alle Zahlen verwerfen, die niedriger als der Median von Set12(zusammengeführt) sind. Wir haben also zu jedem Zeitpunkt gleich große Mengen. Dies kann übrigens nicht parallel erfolgen. Irgendwelche Ideen?

anony
quelle
3
@ John Boker: Eigentlich besteht das Problem aus zwei Teilproblemen: 1) Sortieren Sie die Liste und 2) Holen Sie sich ein Element mit dem Index 5'000'000'000. Ich glaube kaum, dass Zahlen sortiert sind.
Roman
3
@Roman: Das Problem muss nicht aus den beiden von Ihnen beschriebenen Teilproblemen bestehen, z. B. Schnellauswahl. Aber die Schnellauswahl parallelisiert nicht, zumindest nicht trivial. Und natürlich haben Sie Recht, dass es eine ziemlich sinnlose Frage ist, wenn die Zahlen vorsortiert sind.
Steve Jessop
5
@fmsf: Ich glaube nicht, dass ein englischsprachiges Land die lange Milliarde auf Englisch für offizielle Zwecke verwendet. Zum Beispiel haben wir hier in Großbritannien 1974 aufgehört, es zu verwenden. Ich würde die Verwendung von "Milliarde" als eine Million Millionen bezeichnen, in der englischen Sprache als eine perverse Trickfrage, überhaupt keine "echte Milliarde". Natürlich wäre es auf Französisch eine ganz andere Sache, aber die Frage ist nicht auf Französisch.
Steve Jessop
5
Sie müssen nicht sortieren! en.wikipedia.org/wiki/…
Glebm
2
1 Milliarde Zahlen sind nur ein paar Gigabyte Daten. Sie benötigen weder mehrere PCs noch komplexe Algorithmen, um diese Aufgabe zu lösen. Überkomplizieren Sie nicht.
user626528

Antworten:

54

Ah, mein Gehirn hat gerade einen Gang eingelegt, ich habe jetzt einen vernünftigen Vorschlag. Wahrscheinlich zu spät, wenn dies ein Interview gewesen wäre, aber egal:

Maschine 1 wird als "Steuermaschine" bezeichnet, und aus Gründen der Argumentation beginnt sie entweder mit allen Daten und sendet sie in gleichen Paketen an die anderen 99 Maschinen, oder die Daten werden gleichmäßig zwischen den Maschinen verteilt, und sie sendet 1/99 seiner Daten an die anderen. Die Partitionen müssen nicht gleich sein, sondern nur schließen.

Jede andere Maschine sortiert ihre Daten auf eine Weise, die es bevorzugt, zuerst die niedrigeren Werte zu finden. Zum Beispiel eine Quicksortierung, bei der immer zuerst der untere Teil der Partition sortiert wird [*]. Es schreibt seine Daten so schnell wie möglich in aufsteigender Reihenfolge auf die Steuerungsmaschine zurück (unter Verwendung von asynchronem E / A, um die Sortierung fortzusetzen, und wahrscheinlich mit eingeschaltetem Nagle: Experimentieren Sie ein wenig).

Die Steuerungsmaschine führt beim Eintreffen eine 99-Wege-Zusammenführung der Daten durch, verwirft jedoch die zusammengeführten Daten und zählt nur die Anzahl der Werte, die sie gesehen hat. Der Median wird als Mittelwert aus den Werten 1/2 1/2 und 1/2 Milliarde plus 1 berechnet.

Dies leidet unter dem Problem "am langsamsten in der Herde". Der Algorithmus kann erst abgeschlossen werden, wenn jeder Wert, der unter dem Median liegt, von einer Sortiermaschine gesendet wurde. Es besteht eine vernünftige Wahrscheinlichkeit, dass ein solcher Wert in seinem Datenpaket ziemlich hoch ist. Sobald die anfängliche Partitionierung der Daten abgeschlossen ist, ist die geschätzte Laufzeit die Kombination aus der Zeit, um 1/99 der Daten zu sortieren und an den Steuercomputer zurückzusenden, und der Zeit, die die Steuerung benötigt, um die Hälfte der Daten zu lesen . Die "Kombination" liegt irgendwo zwischen dem Maximum und der Summe dieser Zeiten, wahrscheinlich nahe am Maximum.

Mein Instinkt ist, dass es ein verdammt schnelles Netzwerk sein muss, damit Daten über ein Netzwerk schneller gesendet werden als sortiert werden (geschweige denn nur der Median ausgewählt wird). Könnte eine bessere Perspektive sein, wenn davon ausgegangen werden kann, dass das Netzwerk sofort verfügbar ist, z. B. wenn Sie über 100 Kerne mit gleichem Zugriff auf den RAM verfügen, der die Daten enthält.

Da Netzwerk-E / A wahrscheinlich gebunden sind, können Sie möglicherweise einige Streiche spielen, zumindest für die Daten, die zur Steuerungsmaschine zurückkehren. Anstatt beispielsweise "1,2,3, .. 100" zu senden, könnte eine Sortiermaschine möglicherweise eine Nachricht senden, die "100 Werte kleiner als 101" bedeutet. Die Steuermaschine könnte dann eine modifizierte Zusammenführung durchführen, bei der sie den geringsten dieser Werte im oberen Bereich findet und dann allen Sortiermaschinen mitteilt, was es war, damit sie (a) der Steuermaschine mitteilen können, wie viele Werte, die unter diesem Wert "gezählt" werden sollen, und (b) das Senden ihrer sortierten Daten von diesem Punkt an fortsetzen.

Im Allgemeinen gibt es wahrscheinlich ein cleveres Rätselraten, bei dem die Steuerungsmaschine mit den 99 Sortiermaschinen spielen kann.

Dies beinhaltet jedoch Hin- und Rückfahrten zwischen den Maschinen, was meine einfachere erste Version vermeidet. Ich weiß nicht wirklich, wie ich ihre relative Leistung blind einschätzen soll, und da die Kompromisse komplex sind, stelle ich mir vor, dass es viel bessere Lösungen gibt als alles, was ich mir vorstellen werde, vorausgesetzt, dies ist jemals ein echtes Problem.

[*] verfügbarer Stapel zulässig - Ihre Auswahl, welcher Teil zuerst ausgeführt werden soll, ist eingeschränkt, wenn Sie nicht über O (N) zusätzlichen Speicherplatz verfügen. Wenn Sie jedoch über genügend zusätzlichen Platz verfügen, können Sie Ihre Wahl treffen. Wenn Sie nicht über genügend Platz verfügen, können Sie zumindest das verwenden, was Sie zum Schneiden einiger Ecken benötigen, indem Sie den kleinen Teil zuerst für die ersten Partitionen ausführen.

Steve Jessop
quelle
Bitte korrigieren Sie mich, wenn ich falsch liege. Warum führen Sie die 99-Wege-Zusammenführung der Daten durch, da sie erst eintreffen, um sie später zu verwerfen? Ist es stattdessen genug, um die Zahlen zu zählen, wenn sie ankommen?
Sreeprasad
4
@SREEPRASADGOVINDANKUTTY: Der sich wiederholende Schritt besteht darin, den kleinsten Wert aller 99 Kandidaten zu verwerfen und die Anzahl zu erhöhen. Ohne diesen 99-Wege-Zusammenführungsschritt ist es überhaupt nicht sinnvoll, nur alle eingehenden Werte zu zählen. Wenn Sie sie nicht vergleichen, wenn sie eingehen, wissen Sie nicht, dass der Wert, den Sie verwerfen, unter dem Median liegt.
Steve Jessop
Aber gibt es nicht eine geringe Wahrscheinlichkeit, dass eine dieser Partitionen nur Zahlen enthält, die höher als der Median sind, und daher ist jede niedrigere Partition, die sie zurückgibt, höher als der Median, aber da die Kontrolle dies nicht weiß, werden sie als niedriger als die verworfen Median und scheitern ...?
Gullydwarf
@ Gullydwarf: Bei einer Mehrwegezusammenführung wird nur der kleinste der 99 verfügbaren Werte verworfen, von denen jeder der kleinste verbleibende Wert von einer der anderen Maschinen ist. Wenn eine der Partitionen vollständig größer als der Median ist, wird sie erst dann zum kleinsten dieser 99 Werte, wenn der Median überschritten wurde (an diesem Punkt sind wir fertig). Es wird also nicht verworfen.
Steve Jessop
52
sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"
DrPizza
quelle
2
LOL. Funktioniert das wirklich oder wird der OOM-Killer es zerstören, bevor es fertig ist? (auf jedem vernünftigen Computer)
Isak Savo
5
Sollte tun. sort weiß, wie eine Sortierung außerhalb des Kerns durchgeführt wird, damit nicht der Arbeitsspeicher ausgeht.
DrPizza
6
@ Zagfai Ich glaube nicht, dass es zu lange dauern würde; Eine Milliarde Zahlen sind nur 4 GB für 32-Bit-Ints / Floats, 8 GB für 64-Bit-Ints / Doubles. Beides scheint nicht enorm anstrengend.
DrPizza
13
Ich habe gerade einen Intel i5-4200M mit 3,1 GHz (4 Kerne) ausprobiert. Gemäß dem timeBefehl, der auf die gesamte Pipeline angewendet wurde, dauerte es real=36m24s("Wanduhrzeit") user=113m15s ("Parallelzeit", alle Kerne hinzugefügt). Der längste Befehl, weit vor den anderen, war sort, selbst wenn er zu 100% auf meine vier Kerne traf. Der RAM-Verbrauch war sehr akzeptabel.
Morgan Touverey Quilling
11
Führen Sie dann 100 Computer aus, damit Sie 100-mal sicherer sein können, dass das Ergebnis korrekt ist :)
Dos
26

Ich hasse es, hier der Gegenspieler zu sein, aber ich glaube nicht, dass eine Sortierung erforderlich ist, und ich denke, dass jeder Algorithmus, bei dem eine Milliarde / 100-Zahlen sortiert werden, langsam sein wird. Betrachten wir einen Algorithmus auf einem Computer.

1) Wählen Sie zufällig 1000 Werte aus der Milliarde aus und verwenden Sie diese, um eine Vorstellung von der Verteilung der Zahlen, insbesondere eines Bereichs, zu erhalten.

2) Anstatt die Werte zu sortieren, ordnen Sie sie Buckets basierend auf der soeben berechneten Verteilung zu. Die Anzahl der Eimer wird so gewählt, dass der Computer sie effizient handhaben kann, sollte aber ansonsten so groß wie möglich sein. Die Bucket-Bereiche sollten so sein, dass ungefähr die gleiche Anzahl von Werten in jedem Bucket gespeichert wird (dies ist für den Algorithmus nicht kritisch, trägt jedoch zur Effizienz bei. 100.000 Buckets sind möglicherweise angemessen). Notieren Sie die Anzahl der Werte in jedem Bucket. Dies ist ein O (n) -Prozess.

3) Finden Sie heraus, in welchem ​​Bucket-Bereich der Median liegt. Dies kann durch einfaches Untersuchen der Gesamtzahl in jedem Bucket erfolgen.

4) Ermitteln Sie den tatsächlichen Median, indem Sie die Werte in diesem Bucket untersuchen. Sie können hier eine Sortierung verwenden, wenn Sie möchten, da Sie nur vielleicht 10.000 Zahlen sortieren. Wenn die Anzahl der Werte in diesem Bucket groß ist, können Sie diesen Algorithmus erneut verwenden, bis Sie eine ausreichend kleine Anzahl zum Sortieren haben.

Dieser Ansatz wird trivial parallelisiert, indem die Werte zwischen den Computern aufgeteilt werden. Jeder Computer meldet die Gesamtsummen in jedem Bucket an einen Steuercomputer, der Schritt 3 ausführt. In Schritt 4 sendet jeder Computer die (sortierten) Werte im entsprechenden Bucket an den Steuercomputer (Sie können beide Algorithmen auch parallel ausführen). aber es lohnt sich wahrscheinlich nicht).

Der Gesamtprozess ist O (n), da beide Schritte 3 und 4 trivial sind, vorausgesetzt, die Anzahl der Eimer ist groß genug.

DJClayworth
quelle
1
Ich denke, dies liegt zwischen dem Median der Mediane und den Schnellauswahlalgorithmen. en.wikipedia.org/wiki/Selection_algorithm
Dimath
In Schritt 4 enthalten die Eimer möglicherweise nicht nur 10.000. Es kann vorkommen, dass die Verteilung zur Mitte hin verschoben ist, wo sie beispielsweise 80% der Daten enthält, was immer noch riesig ist.
Nur die Hälfte des
Bearbeitet, um dies zu berücksichtigen.
DJClayworth
Ich mag diesen Ansatz.
Al Kepp
4
Die Leistung ist in diesem Algorithmus nicht O (n): Die meisten Zahlen könnten in den "Median" -Eimer fallen, und die Leistung könnte so schlecht sein wie das Sortieren von allem.
Sklivvz
12

Eine Milliarde ist eigentlich eine ziemlich langweilige Aufgabe für einen modernen Computer. Wir sprechen hier von 4 GB im Wert von 4 Byte Ganzzahlen ... 4 GB ... das ist der RAM einiger Smartphones.

public class Median {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int[] numbers = new int[1_000_000_000];

        System.out.println("created array after " +  (System.currentTimeMillis() - start) + " ms");

        Random rand = new Random();
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = rand.nextInt();
        }

        System.out.println("initialized array after " + (System.currentTimeMillis() - start) + " ms");

        Arrays.sort(numbers);

        System.out.println("sorted array after " + (System.currentTimeMillis() - start) + " ms");

        if (numbers.length % 2 == 1) {
            System.out.println("median = " + numbers[numbers.length / 2 - 1]);
        } else {
            int m1 = numbers[numbers.length / 2 - 1];
            int m2 = numbers[numbers.length / 2];
            double m = ((long) m1 + m2) / 2.0;
            System.out.println("median = " + new DecimalFormat("#.#").format(m));
        }
}

Ausgabe auf meinem Computer:

created array after 518 ms
initialized array after 10177 ms
sorted array after 102936 ms
median = 19196

Dies ist auf meinem Computer innerhalb von weniger als zwei Minuten (1:43 davon 0:10 sollen Zufallszahlen generieren) mit einem einzigen Kern abgeschlossen und führt sogar eine vollständige Sortierung durch. Eigentlich nichts Besonderes.

Dies ist sicherlich eine interessante Aufgabe für größere Mengen von Zahlen. Ich möchte hier nur einen Punkt hervorheben: Eine Milliarde sind Erdnüsse. Überlegen Sie also zweimal, bevor Sie komplexe Lösungen für überraschend einfache Aufgaben einsetzen;)

sfussenegger
quelle
Das habe ich in meiner Antwort hier gesagt :-) stackoverflow.com/a/31819222/363437
vidstige
1
@vidstige Ich habe es ehrlich gesagt nicht gelesen, aber du hast recht. meine antwort ist aber sicherlich
praxisnaher
Das ist jedoch nicht der Median, der Median ist (numbers[numbers.length / 2]+numbers[numbers.length / 2+1])/2wenn numbers.lengthist gerade und numbers[numbers.length / 2]nur wenn numbers.lengthist ungerade.
Sklivvz
@Sklivvz korrekt, aber es sollte keinen merklichen Einfluss auf die Zeit haben, die zur Berechnung des Medians benötigt wird.
Vidstige
1
@Sklivvz du hast natürlich recht. Ich habe gerade die Medianberechnung aktualisiert. Der Rest der Antwort ändert sich jedoch nicht.
sfussenegger
10

Die Schätzung von Ordnungsstatistiken wie Median und 99. Perzentil kann mit Algorithmen wie T-Digest oder Q-Digest effizient verteilt werden .

Mit beiden Algorithmen erzeugt jeder Knoten einen Digest, der die Verteilung der lokal gespeicherten Werte darstellt. Die Digests werden an einem einzelnen Knoten gesammelt, zusammengeführt (wodurch die Verteilungen effektiv summiert werden), und der Median oder ein anderes Perzentil kann dann nachgeschlagen werden.

Dieser Ansatz wird von elasticsearch und vermutlich BigQuery verwendet ( gemäß der Beschreibung der Funktion QUANTILES).

Richard Poole
quelle
5

Der Median für diesen Satz von Zahlen

2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89, 97

ist 67.

Der Median für diesen Satz von Zahlen

2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89

ist 40.

Angenommen, die Frage war ungefähr 1.000.000.000 ganze Zahlen (x), wobei 0> = x <= 2.147.483.647, und das OP suchte (Element (499.999.999) + Element (500.000.000)) / 2 (wenn die Zahlen sortiert waren). Auch unter der Annahme, dass alle 100 Computer alle gleich waren.

mit meinem Laptop und GigE ...

Was ich fand, war, dass mein Laptop in 1,3 Sekunden 10.000.000 Int32 sortieren kann. Eine grobe Schätzung wäre also, dass eine Milliardenzahlsortierung 100 x 1,3 Sekunden (2 Minuten 10 Sekunden) dauern würde;).

Eine Schätzung einer Einweg-Dateiübertragung einer 40-MB-Datei auf einem Gigabit-Ethernet beträgt 0,32 Sekunden. Dies bedeutet, dass die sortierten Ergebnisse aller Computer in ungefähr 32 Sekunden zurückgegeben werden (Computer 99 hat seine Datei erst 30 Sekunden nach dem Start erhalten). Von dort sollte es nicht lange dauern, die niedrigsten 499.999.998 Zahlen zu verwerfen, die nächsten 2 zu addieren und durch 2 zu teilen.

dbasnett
quelle
3
Downwähler Kommentar? Es würde mir helfen zu verstehen, wie ich es besser machen kann.
Dbasnett
5
Ich bin nicht der Down-Wähler, aber das Sortieren von einer Milliarde Zahlen dauert nicht 100-mal so lange wie das Sortieren von 10 Millionen, da die Komplexität beim Sortieren einer Liste im schlimmsten Fall O (n log n) ist. Das Sortieren ist auch um Größenordnungen langsamer, wenn Ihnen der Speicher ausgeht und Sie mit dem Sortieren auf der Festplatte beginnen müssen.
Richard Poole
Ich denke, Sie sind auf dem richtigen Weg. Wenn das Ziel eine schnellstmögliche Antwort ist, ist das Sortieren auf mehreren Computern möglicherweise eine gute Idee. Wenn das Ziel jedoch die niedrigste durchschnittliche Zeit ist, ist jede Maschine, die ihre eigene Suche durchführt, sinnvoller.
Charlie
Angenommen, sie haben den gleichen Faktor (den sie wahrscheinlich aufgrund von Speicherproblemen nicht haben), dann a*(1e7)log(1e7) = 1.3sec=> a = 1.6e-9sec => a*(1e9)log(1e9) ~ 167sec, also war Ihre Schätzung nicht so falsch.
Bcorso
Ihre Schätzungen sind viel zu grob. Erstens gehen einige Sortieralgorithmen im schlimmsten Fall als o (n ^ 2) (z. B. bei der häufig verwendeten Quicksortierung). Zweitens haben Sie einen Testdatensatz ausgewählt, der ungefähr der Größe Ihres L2-Caches entspricht. Dies verzerrt die Ergebnisse. Drittens nehmen Sie (wie viele andere Antwortende) an, dass "Zahl" "Ganzzahl" bedeutet. Dies kann Float, Double oder Decimal bedeuten, die sehr unterschiedliche Leistungsmerkmale aufweisen.
Sklivvz
5

Dies mag die Leute überraschen, aber wenn die Zahlen ganze Zahlen sind, die in 32-Bit (oder kleiner) passen - machen Sie einfach eine Bucket-Sortierung! Benötigt nur 16 GB RAM für eine beliebige Anzahl von 32-Bit-Ints und läuft in O (n), was alle verteilten Systeme für vernünftige n, z. B. eine Milliarde, übertreffen sollte.

Sobald Sie die sortierte Liste haben, ist es trivial, den Median auszuwählen. Tatsächlich müssen Sie die sortierte Liste nicht erstellen, sondern sollten nur die Buckets betrachten.

Eine einfache Implementierung ist unten gezeigt. Funktioniert nur für 16-Bit-Ganzzahlen, die Erweiterung auf 32-Bit sollte jedoch einfach sein.

#include <stdio.h>
#include <string.h>

int main()
{
    unsigned short buckets[65536];
    int input, n=0, count=0, i;

    // calculate buckets
    memset(buckets, 0, sizeof(buckets));
    while (scanf("%d", &input) != EOF)
    {
        buckets[input & 0xffff]++;
        n++;
    }

    // find median 
    while (count <= n/2)
    {
        count += buckets[i++];
    }

    printf("median: %d\n", i-1);

    return 0;
}

Verwenden einer Textdatei mit einer Milliarde (10 9 ) Zahlen und Ausführen mit timeÄhnlichem

time ./median < billion

ergibt eine Laufzeit auf meinem Computer 1m49.293s. Die meiste Laufzeit ist wahrscheinlich auch Festplatten-E / A.

vidstige
quelle
Dies beantwortet die Frage nicht wirklich und beruht auf Annahmen. Zum Beispiel wissen Sie nicht einmal, dass es sich um ganze Zahlen handelt.
Sklivvz
Inwiefern beantwortet es die Frage nicht? Und ja, meine Antwort geht davon aus, dass die Zahlen ganze Zahlen sind. Ich habe versucht, meine Annahmen klar zu formulieren.
Vidstige
Sie scheinen nicht zu behaupten, dass Ganzzahlen eine Annahme sind, und Sie sprechen auch nicht darüber, wie die 100 Computer verwendet werden sollen, nach denen das OP fragt. Sie können den Median auf einem Knoten berechnen, aber das ist nicht die "beste" Lösung, es sei denn, Sie zeigen, warum. Außerdem ist die Radix-Sortierung nicht o (n), wenn die Anzahl der Ziffern variiert, was laut en.wikipedia.org/wiki/Radix_sort#Efficiency in diesem Fall sicherlich o (n log n) ist
Sklivvz
Ich beginne mit der Aussage "Wenn die Ganzzahlen klein genug sind, um in eine 32-Bit- Ganzzahl zu passen " ... Die Radix-Sortierung ist O (n) für eine konstante Wortgröße w, wie in dem von Ihnen geposteten Link ausführlich beschrieben. Hier
gehe
1
Was Sie mit den 99 anderen Computern machen, ist in dieser Antwort nicht relevant. Sie können sie übereinander stapeln, um eine Pyramide zu bilden, oder sie verbrennen. Oder ignoriere sie einfach.
Vidstige
3

Seltsamerweise denke ich, wenn Sie über genügend Computer verfügen, ist das Sortieren besser als die Verwendung von O(n)Median-Finding-Algorithmen. (Wenn Ihre Kerne jedoch nicht sehr, sehr langsam sind, würde ich nur einen verwenden und einen O(n)Median-Finding-Algorithmus für nur 1e9-Zahlen verwenden. Wenn Sie jedoch 1e12 hätten, wäre dies möglicherweise weniger praktisch.)

Nehmen wir an, wir haben mehr als nur log n Kerne, um dieses Problem zu lösen, und wir kümmern uns nicht um den Stromverbrauch, sondern bekommen nur schnell die Antwort. Nehmen wir weiter an, dass dies eine SMP-Maschine ist, auf der alle Daten bereits im Speicher geladen sind. (Die 32-Kern-Maschinen von Sun sind beispielsweise von diesem Typ.)

Ein Thread zerlegt die Liste blind in gleich große Stücke und weist die anderen M-Threads an, sie zu sortieren. Diese Threads tun dies fleißig und (n/M) log (n/M)rechtzeitig. Sie geben dann nicht nur ihre Mediane zurück, sondern beispielsweise auch ihre 25. und 75. Perzentile (perverse Worst-Cases sind besser, wenn Sie leicht unterschiedliche Zahlen wählen). Jetzt haben Sie 4 Millionen Datenbereiche. Anschließend sortieren Sie diese Bereiche und arbeiten die Liste nach oben durch, bis Sie eine Zahl finden, bei der Sie die Hälfte Ihrer Daten verworfen haben , wenn Sie jeden Bereich wegwerfen, der kleiner ist oder die Zahl enthält. Das ist Ihre Untergrenze für den Median. Machen Sie dasselbe für die Obergrenze. Dies dauert ungefähr so ​​lange M log Mund alle Kerne müssen darauf warten, also ist es wirklich verschwenderischM^2 log Mmögliche Zeit. Jetzt muss Ihr einzelner Thread die anderen anweisen, alle Daten außerhalb des Bereichs zu werfen (Sie sollten bei jedem Durchgang etwa die Hälfte wegwerfen) und wiederholen - dies ist eine trivial schnelle Operation, da die Daten bereits sortiert sind. Sie sollten dies nicht öfter wiederholen müssen, log(n/M)bevor es schneller ist, nur die verbleibenden Daten zu erfassen und einen Standard- O(n)Median-Finder zu verwenden.

Die Gesamtkomplexität ist also so etwas wie O((n/M) log (n/M) + M^2 log M log (n/M)). Dies ist also schneller als die O(n)Mediansortierung auf einem Kern, wenn M >> log(n/M)und M^3 log M < n, was für das von Ihnen beschriebene Szenario gilt.

Ich denke, das ist eine wirklich schlechte Idee, wenn man bedenkt, wie ineffizient es ist, aber es ist schneller.

Rex Kerr
quelle
o (n / M log (n / M)) ist buchstäblich o (n log n), weil o (n / M log (n / M)) = 1 / M o (n (log n - log M) ) = o (n log n). Man kann es nicht wirklich mit so einem o (n) vergleichen, da das "o" im Grunde genommen "proportional zu für großes sehr n mit einer nicht spezifizierten Konstante" bedeutet. Wenn Sie diese Konstanten nicht kennen, können Sie sie nicht vergleichen, aber für ausreichend großes N sind die Konstanten nicht dominant. Bei niedrigeren Zahlen sind alle Wetten ungültig. O (1) kann leicht langsamer sein als o (n!).
Sklivvz
@Sklivvz - nund Msind die Variablen, die beliebig skaliert werden können, also enthält man beide. Insbesondere habe ich das postuliert M> log n, was bedeutet, dass Sie sich auch darum kümmern müssen, wenn Sie sich dafür interessieren, dass es nicht n log nnur gerecht nist M.
Rex Kerr
3

Dies kann schneller erfolgen als der gewählte Algorithmus (n log n)

- Verteilter Auswahlalgorithmus für Ordnungsstatistiken - O (n)
Vereinfachen Sie das Problem mit dem ursprünglichen Problem, die k-te Zahl in einem unsortierten Array zu finden.
- Sortierhistogramm zählen O (n)
Sie müssen einige Eigenschaften über den Bereich der Zahlen annehmen - kann der Bereich in den Speicher passen? - Externe Zusammenführungssortierung - O (n log n) - oben beschrieben
Sie sortieren die Zahlen im Grunde genommen beim ersten Durchgang und finden dann den Median beim zweiten Durchgang.
- Wenn etwas über die Verteilung der Zahlen bekannt ist, können andere Algorithmen erzeugt werden.

Weitere Details und die Implementierung finden Sie unter:
http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html

user1712376
quelle
2

Ein Computer ist mehr als genug, um das Problem zu lösen.

Nehmen wir jedoch an, dass es 100 Computer gibt. Das einzig komplexe, was Sie tun sollten, ist die Liste zu sortieren. Teilen Sie es auf 100 Teile auf, senden Sie ein Teil an jeden Computer, lassen Sie es dort sortieren und führen Sie danach Teile zusammen.

Nehmen Sie dann die Nummer aus der Mitte der sortierten Liste (dh mit dem Index 5 000 000 000).

römisch
quelle
3
Wie auch immer, jetzt ist mein Repräsentant ziemlich rund :)
Roman
Das Zusammenführen ist bestenfalls O (n), und Sie können den Median auf einem einzelnen Kern in O (n) finden, so dass dies viel zusätzliche Arbeit ohne Gewinn zu schaffen scheint.
Rex Kerr
2

Das hängt von Ihren Daten ab. Das schlimmste Szenario ist, dass es sich um gleichmäßig verteilte Zahlen handelt.

In diesem Fall finden Sie den Median in O (N) -Zeit wie in diesem Beispiel:

Angenommen, Ihre Zahlen sind 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3 (Bereich 1-10) .

Wir erstellen 3 Eimer: 1-3, 4-7, 8-10. Beachten Sie, dass oben und unten gleich groß sind.

Wir füllen die Eimer mit den Zahlen, zählen, wie viele in jede fallen, die maximale und die minimale

  • niedrig (5): 2,1,1,3,3, min 1, max 3
  • Mitte (10): 7,5,6,4,4,6,4,7,4,4, min 4, max 7
  • hoch (5): 10, 10, 8, 9, 9, min 8, max 10

Der Mittelwert fällt in den mittleren Eimer, den Rest ignorieren wir

Wir erstellen 3 Eimer: 4, 5-6, 7. Niedrig beginnt mit einer Zählung von 5 und mit einem Maximum von 3 und hoch mit einer Min von 8 und einer Zählung von 5.

Für jede Zahl zählen wir, wie viele in den niedrigen und hohen Eimer fallen, den maximalen und den minimalen, und behalten den mittleren Eimer.

  • altes Tief (5)
  • niedrig (5): 4, 4, 4, 4, 4, max 4
  • Mitte (3): 5,6,6
  • hoch (2): 7, 7, min 7
  • altes Hoch (5)

Jetzt können wir den Median direkt berechnen: Wir haben eine solche Situation

old low    low          middle  high  old high
x x x x x  4 4 4 4 4 4   5 6 6  7 7   x x x x x

Der Median ist also 4,5.

Angenommen, Sie wissen etwas über die Verteilung, können Sie die Definition der Bereiche zur Optimierung der Geschwindigkeit genau einstellen. In jedem Fall sollte die Leistung mit O (N) gehen, da 1 + 1/3 + 1/9 ... = 1,5

Sie benötigen aufgrund von Kantenfällen min und max (z. B. wenn der Median der Durchschnitt zwischen dem Maximum des alten Tiefs und dem nächsten Element ist).

Alle diese Vorgänge können parallelisiert werden. Sie können jedem Computer 1/100 der Daten geben und die 3 Buckets in jedem Knoten berechnen. Anschließend können Sie den Bucket verteilen, den Sie behalten. Dadurch können Sie das Netzwerk wieder effizient nutzen, da jede Nummer durchschnittlich 1,5-mal übergeben wird (also O (N)). Sie können das sogar übertreffen, wenn Sie nur die minimalen Zahlen zwischen den Knoten übergeben (z. B. wenn Knoten 1 100 Zahlen und Knoten 2 150 Zahlen hat, kann Knoten 2 Knoten 1 25 Zahlen geben).

Wenn Sie nicht mehr über die Verteilung wissen, bezweifle ich, dass Sie hier besser als O (N) abschneiden können, da Sie die Elemente tatsächlich mindestens einmal zählen müssen.

Sklivvz
quelle
1
Ist das nicht der schlimmste Fall (für Ihren Algorithmus), wenn alle Zahlen gleich sind? Wenn ich richtig liege, wird keiner Ihrer Eimer außer dem mittleren mit allen Elementen gefüllt. Daher müssen Sie jedes Mal alle Elemente durchlaufen und dabei exponentiell schnell bis zur Mitte des Intervalls voranschreiten. Ich glaube, dass es O(n log n)in diesem Fall ein wäre. Macht das Sinn ? Übrigens mag ich Ihre Idee
Dici
1
@Dici nicht wirklich: Erstens können Sie das "egal" -Szenario leicht abkürzen, weil Sie min und max kennen. Wie ich in der Antwort sagte, könnte das Wissen um die Verteilung Ihre Auswahl an Eimern beeinflussen. zweitens würde es noch dauern o(n)+o(n/3)+o(n/9)+...was noch ist o(n)und nicht o(n log n).
Sklivvz
Auf der anderen Seite gibt es wahrscheinlich ein anderes Worst-Case-Szenario, eine U-förmige Verteilung. Ich muss ein bisschen darüber nachdenken, den schlimmsten Fall formalisieren, aber es könnte möglicherweise schlimmer sein als o(n)in diesem Fall, mit der naiven Partitionierung.
Sklivvz
Mmm ja, die Min und Max würden helfen, den "alle gleichen" Fall ziemlich einfach zu handhaben
Dici
2

Eine einfachere Methode besteht darin, gewichtete Zahlen zu haben.

  • Teilen Sie das große Set auf Computer auf
  • Sortieren Sie jeden Satz
  • Durchlaufen Sie die kleine Menge und berechnen Sie die Gewichte für wiederholte Elemente
  • Füge jeweils 2 Sätze zu 1 zusammen (jeder ist bereits sortiert) und aktualisiere die Gewichte
  • Zusammenführen von Sätzen, bis Sie nur noch einen Satz erhalten
  • Durchlaufen Sie diesen Satz und sammeln Sie Gewichte, bis Sie OneBillion / 2 erreichen
Ziad Nasser
quelle
1

Teilen Sie die 10 ^ 9 Zahlen, 10 ^ 7, auf jeden Computer ~ 80 MB auf jedem. Jeder Computer sortiert seine Nummern. Dann sortiert Computer 1 seine eigenen Zahlen mit denen von Computer 2, Computer 3 und 4 usw. Dann schreibt Computer 1 die Hälfte der Zahlen zurück auf 2, 3 bis 4 usw. Dann sortiert 1 Zusammenführen die Zahlen von Computern 1,2,3,4, schreibt sie zurück. Und so weiter. Abhängig von der Größe des Arbeitsspeichers auf den Computern, bei denen Sie möglicherweise nicht bei jedem Schritt alle Zahlen auf die einzelnen Computer zurückschreiben, können Sie die Zahlen möglicherweise für mehrere Schritte auf Computer 1 akkumulieren, aber Sie rechnen nach.

Oh, endlich den Mittelwert der 500000000. und 500000001. Werte ermitteln (aber überprüfen Sie, ob dort genügend 00s vorhanden sind, habe ich nicht).

EDIT: @Roman - Nun, wenn Sie es nicht glauben können, obwohl es wahr ist, dann macht es keinen Sinn, die Wahrheit oder Falschheit des Satzes zu enthüllen. Was ich damit sagen wollte war, dass Brute Force in einem Rennen manchmal klug schlägt. Ich habe ungefähr 15 Sekunden gebraucht, um einen Algorithmus zu entwickeln, von dem ich überzeugt bin, dass ich ihn implementieren kann, der funktioniert und der an eine Vielzahl von Eingangsgrößen und Computerzahlen angepasst und an die Eigenschaften der Computer und Computer angepasst werden kann Netzwerkvereinbarungen. Wenn Sie oder jemand anderes 15 Minuten brauchen, um einen ausgefeilteren Algorithmus zu entwickeln, habe ich einen Vorteil von 14 Minuten und 45 Sekunden, um meine Lösung zu codieren und zu starten.

Aber ich gebe frei zu, dass dies alles eine Behauptung ist, ich habe nichts gemessen.

Hochleistungsmarke
quelle
Hier werden nur alle Zahlen zusammengeführt. Können wir es besser machen mit: - "Wir können den Median zweier sortierter Listen in Logn-Zeit finden. N ist die Länge jeder Liste."
Anony
1
@anony - Während Sie Ihre eigene Frage beantworten, werde ich meine Lösung codieren, testen und fertigstellen. Ich erwarte, dass es bessere Wege gibt, aber manchmal lässt mich das Parallelisieren eines einfachen Weges frei, um mich an den wirklich schwierigen Problemen zu kratzen.
High Performance Mark
Hast du es wirklich in 7 Minuten geschafft? Ich kann das nicht glauben, auch wenn es wahr ist. Ich habe die ähnliche Aufgabe erledigt (es war eine Universitätsaufgabe) und es dauerte ungefähr 2 Stunden, um alle Remoting-Inhalte zu implementieren und zu testen (ich habe Java RMI verwendet).
Roman
Ich verstehe, was Sie sagen, aber aus dem gleichen Grund hat DrPizza eine noch schnellere Lösung, bei der alle Daten auf einem einzelnen Knoten sortiert und die anderen 99 ignoriert werden. Keiner von uns weiß, wie teuer Daten sind Transfer sollte in Betracht gezogen werden, also wählen wir alle nur einen Kompromiss, der vage plausibel klingt. Ihre Lösung überträgt alle Daten mehrmals, daher bin ich etwas misstrauisch, aber es ist sicherlich eine Lösung.
Steve Jessop
'vage plausibel' - das ist gut genug für mich @Steve! Besonders als Antwort auf eine vage unplausible Frage.
High Performance Mark
1

Dies kann auf Knoten erfolgen, die Daten verwenden, die nicht wie folgt nach Knoten sortiert sind (z. B. aus Protokolldateien).

Es gibt 1 übergeordneten Knoten und 99 untergeordnete Knoten. Die untergeordneten Knoten haben zwei API-Aufrufe:

  • stats (): Gibt min, max und count zurück
  • compare (median_guess): Gibt den übereinstimmenden Zählwert zurück, zählt kleiner als der Wert und zählt größer als der Wert

Der übergeordnete Knoten ruft auf allen untergeordneten Knoten stats () auf und notiert das Minimum und Maximum aller Knoten.

Eine binäre Suche kann nun folgendermaßen durchgeführt werden:

  1. Halbieren Sie die minimale und maximale Abrundung - dies ist die mittlere 'Vermutung'
  2. Wenn der Wert größer als die Anzahl größer als der Wert kleiner ist, setzen Sie das Minimum auf die Schätzung
  3. Wenn die Anzahl größer als die Anzahl kleiner als kleiner ist, setzen Sie das Maximum auf die Schätzung
  4. Wenn die Anzahl ungerade ist, beenden Sie, wenn Minimum und Maximum gleich sind
  5. Wenn die Zählung gerade beendet ist, wenn Maximum <= Minimum + rate.match_count Dies kann auf Knoten wie folgt auf unsortierten Daten (z. B. aus Protokolldateien) erfolgen.

Es gibt 1 übergeordneten Knoten und 99 untergeordnete Knoten. Die untergeordneten Knoten haben zwei API-Aufrufe:

  • stats (): Gibt min, max und count zurück
  • compare (median_guess): Gibt den übereinstimmenden Zählwert zurück, zählt kleiner als der Wert und zählt größer als der Wert

Der übergeordnete Knoten ruft auf allen untergeordneten Knoten stats () auf und notiert das Minimum und Maximum aller Knoten.

Eine binäre Suche kann nun folgendermaßen durchgeführt werden:

  1. Halbieren Sie die minimale und maximale Abrundung - dies ist die mittlere 'Vermutung'
  2. Wenn der Wert größer als die Anzahl größer als der Wert kleiner ist, setzen Sie das Minimum auf die Schätzung
  3. Wenn die Anzahl größer als die Anzahl kleiner als kleiner ist, setzen Sie das Maximum auf die Schätzung
  4. Wenn die Anzahl ungerade ist, beenden Sie, wenn Minimum und Maximum gleich sind
  5. Wenn die Zählung gerade beendet ist, wenn Maximum <= Minimum + rate.match_count

Wenn die Werte () und compare () mit einer O (N / Mlogn / M) -Sortierung vorberechnet werden könnten, dann eine O (N / M) -Vorberechnung mit einer Speicherkomplexität von O (N) für die Vorberechnung Berechnung. Dann könnten Sie compare () in konstanter Zeit ausführen, sodass das Ganze (einschließlich Vorberechnung) in O (N / MlogN / M) + O (logN) ausgeführt wird.

Lassen Sie mich wissen, wenn ich einen Fehler gemacht habe!

Teambob
quelle
Ja, ich würde nur binäre Suche machen. Würde Netzwerkbandbreite sparen, wenn jeder Computer nur ein paar Mal aufgerufen wird. Außerdem könnte jede Maschine einen "Drehpunkt" haben, bei dem die Nummern auf beiden Seiten des Drehpunkts ausgetauscht werden, um Zeit zu sparen. (Pivot wäre die vorherige Schätzung des Medians, so dass beim nächsten Mal nur alle Zahlen auf einer Seite des Pivots durchlaufen werden müssen)
Robert King
0

Wie wäre es damit: - Jeder Knoten kann 1 Milliarde / 100 Zahlen annehmen. An jedem Knoten können die Elemente sortiert und der Median gefunden werden. Finden Sie den Median der Mediane. Wir können durch Aggregation der Anzahl von Zahlen, die kleiner als der Median des Medians auf allen Knoten sind, herausfinden, welche x%: y% Aufteilung der Median des Medians erfolgt. Bitten Sie nun alle Knoten, Elemente zu löschen, die kleiner als der Median der Mediane sind (Beispiel: 30%: 70% Aufteilung). 30% -Zahlen werden gelöscht. 70% von 1 Milliarde sind 700 Millionen. Jetzt können alle Knoten, die weniger als 3 Millionen Knoten gelöscht haben, diese zusätzlichen Knoten an einen Hauptcomputer zurücksenden. Der Hauptcomputer verteilt sich so um, dass jetzt alle Knoten fast die gleiche Anzahl von Knoten haben (7 Millionen). Jetzt, da das Problem auf 700 Millionen reduziert ist, geht es weiter, bis wir einen kleineren Satz haben, der auf einem Comp berechnet werden kann.

anony
quelle
Im Wesentlichen reduzieren wir das Problem immer um mindestens 30% und erreichen dadurch viel paralleles Rechnen. Jeder Knoten beginnt mit 10 Millionen und reduziert seinen Datensatz in jeder Iteration um 30%.
Anony
In der ersten Iteration suchen wir nach der 500-millionensten Zahl. In der zweiten Iteration - wenn die Anzahl der gelöschten Zahlen 300 Millionen beträgt, suchen wir nach der 200-Millionen-Zahl und so weiter ...
anony
2
Das sieht so aus, als wäre es auf dem richtigen Weg, aber Sie erklären nicht ganz klar, wie Sie vermeiden können, den Median versehentlich mit Ihrer 30% / 70% -Split wegzuwerfen. Nehmen Sie das folgende Gegenbeispiel: Angenommen, Ihre ersten 29% sind alle Nullen, und alle anderen Blöcke zählen bis 1000, und jeder Satz von Blöcken ist einer mehr als der letzte. Der Median des 30. Perzentils wirft alle 29% der Daten weg und knapp die Hälfte von 61% der Daten, was 29 + 30% = 59% der Daten entspricht. Ups, wir haben gerade den wahren Median rausgeworfen! Anscheinend meinst du das nicht so, oder zumindest meinst du es klüger als ich es interpretiert habe.
Rex Kerr
0

Lassen Sie uns zunächst herausfinden, wie Sie einen Median von n Zahlen auf einer einzelnen Maschine finden: Ich verwende im Grunde eine Partitionierungsstrategie.

Problem: Auswahl (n, n / 2): Finden Sie die n / 2-te Zahl aus der kleinsten Zahl.

Sie wählen beispielsweise das mittlere Element k und partitionieren die Daten in zwei Unterarrays. Die erste enthält alle Elemente <k und die zweite enthält alle Elemente> = k.

Wenn sizeof (1. Unterarray)> = n / 2 ist, wissen Sie, dass dieses Unterarray den Median enthält. Sie können dann das 2. Sub-Array abwerfen. Lösen Sie diese Problemauswahl (Größe des 1. Subarrays, n / 2) .

In diesem Fall werfen Sie dieses 1. Subarray ab und lösen die Auswahl (2. Subarray, n / 2 - Größe von (1. Subarray))

Mach es rekursiv.

Zeitkomplexität ist O (n) erwartete Zeit.

Wenn wir nun viele Maschinen haben, müssen wir in jeder Iteration ein Array zum Teilen verarbeiten und das Array in verschiedene Maschinen verteilen. Jede Maschine verarbeitet ihren Array- Block und sendet die Zusammenfassung an die Hub-Steuerungsmaschine zurück, dh die Größe des 1. Subarrays und die Größe des 2. Subarrays. Die Hub-Maschinen addieren Zusammenfassungen und entscheiden, welches Subarray (1. oder 2.) weiter verarbeitet werden soll und 2. Parameter der Auswahl und senden es an jede Maschine zurück. und so weiter.

Dieser Algorithmus kann sehr sauber mit Map Reduce implementiert werden?

Wie sieht es aus?

xyz
quelle
0

Ich denke, Steve Jessops Antwort wird die schnellste sein.

Wenn die Größe der Netzwerkdatenübertragung der Engpass ist, gibt es hier einen anderen Ansatz.

Divide the numbers into 100 computers (10 MB each). 
Loop until we have one element in each list     
    Find the meadian in each of them with quickselect which is O(N) and we are processing in parallel. The lists will be partitioned at the end wrt median.
    Send the medians to a central computer and find the median of medians. Then send the median back to each computer. 
    For each computer, if the overall median that we just computed is smaller than its median, continue in the lower part of the list (it is already partitioned), and if larger in the upper part.
When we have one number in each list, send them to the central computer and find and return the median.
Cem
quelle
Jeweils 32 MB?
Dici
Was meinst du mit Weiter im unteren Teil der Liste?
Ruthvik Vaila
0

Ich würde es so machen:

Am Anfang arbeiten alle 100 daran, die höchste und die niedrigste Zahl zu finden. Jeder Computer hat seinen Teil der Datenbank / Datei, die er abfragt.

Wenn die höchsten und niedrigsten Zahlen gefunden werden, liest ein Computer die Daten und verteilt jede Zahl gleichmäßig an den Rest der 99; die Zahlen werden in gleichen Intervallen verteilt; (einer kann von -100 Millionen bis 0 nehmen, ein anderer - von 0 bis 100 Millionen usw.);

Während des Empfangs von Nummern sortiert jeder der 99 Computer diese bereits.

Dann ist es einfach, den Median zu finden ... Sehen Sie, wie viele Zahlen jeder Computer hat, addieren Sie alle (die Summe der Anzahl der Zahlen, nicht die Zahlen selbst), dividieren Sie durch 2; Berechnen Sie, auf welchem ​​Computer die Nummer und an welchem ​​Index angegeben ist.

:) voilla

PS Es scheint, dass hier viel Verwirrung herrscht. der MEDIAN - ist die ZAHL IN DER MITTE EINER SORTIERTEN LISTE VON ZAHLEN!

Johny
quelle
0

Sie können die Turnierbaummethode verwenden, um den Median zu ermitteln. Wir können einen Baum mit 1000 Urlaubsknoten erstellen, sodass jeder Blattknoten ein Array ist. Wir führen dann n / 2 Turniere zwischen den verschiedenen Arrays durch. Der Wert auf der Wurzel nach den n / 2 Turnieren ist das Ergebnis.

http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/

Karan Kapoor
quelle
0

Wenn die Zahlen nicht eindeutig sind und nur zu einem bestimmten Bereich gehören, dh wiederholt werden, besteht eine einfache Lösung darin, die Zahlen gleichmäßig auf 99 Maschinen zu verteilen und eine Maschine als Master zu behalten. Jetzt iteriert jede Maschine über die angegebenen Zahlen und speichert die Anzahl jeder Zahl in einem Hash-Satz. Jedes Mal, wenn die Nummer in dem diesem bestimmten Computer zugewiesenen Nummernsatz wiederholt wird, wird die Anzahl im Hash-Satz aktualisiert.

Alle Maschinen geben dann ihren Hash-Satz an die Master-Maschine zurück. Die Master-Maschine kombiniert die Hash-Sätze und summiert die Anzahl des gleichen Schlüssels, der in einem Hash-Satz gefunden wurde. Zum Beispiel hatte der Hash-Satz von Maschine Nr. 1 einen Eintrag von ("1", 7), und der Hash-Satz von Maschine Nr. 2 hatte einen Eintrag von ("1", 9), so dass der Master-Computer beim Kämmen der Hash-Sätze einen Eintrag von macht ("1", 16) und so weiter.

Sobald die Hash-Sets zusammengeführt wurden, sortieren Sie einfach die Schlüssel. Jetzt können Sie das (n / 2) -te Element und das (n + 2/2) -te Element leicht aus dem sortierten Hash-Set finden.

Diese Methode ist nicht vorteilhaft, wenn die Milliardenzahlen unterschiedlich sind.

Eric B.
quelle
0

Angenommen, Sie wissen, dass die Anzahl der unterschiedlichen Ganzzahlen (sagen wir) 4 Milliarden beträgt. Dann können Sie sie in 64.000 Buckets zusammenfassen und eine verteilte Anzahl für jeden Bucket von jedem Computer im Cluster (100 Computer) erhalten. Kombinieren Sie all diese Zählungen. Suchen Sie nun den Bucket mit dem Median und fragen Sie diesmal nur nach Buckets für die 64k-Elemente, die in Ihrem Ziel-Bucket liegen würden. Dies erfordert O (1) (speziell 2) Abfragen über Ihren "Cluster". : D.

Gandharv Garg
quelle
0

Mein Penny wert, nach all dem, was schon von anderen angesprochen wurde:

Das Ermitteln des Medians auf einem einzelnen Computer lautet O (N): https://en.wikipedia.org/wiki/Selection_algorithm .

Das Senden von N Nummern an 100 Maschinen ist ebenfalls O (N). Um die Verwendung von 100 Maschinen interessant zu machen, muss entweder die Kommunikation relativ schnell sein oder N ist so groß, dass eine einzelne Maschine nicht damit umgehen kann, solange N / 100 machbar ist, oder wir möchten nur das mathematische Problem betrachten, ohne uns darum zu kümmern Datenkommunikation.

Um es kurz zu machen, gehe ich daher davon aus, dass wir die Zahlen innerhalb angemessener Grenzen senden / verteilen können, ohne die Effizienzanalyse zu beeinflussen.

Betrachten Sie dann den folgenden Ansatz, bei dem eine Maschine als "Master" für eine allgemeine Verarbeitung zugewiesen wird. Dies ist vergleichsweise schnell, sodass der "Master" auch an den allgemeinen Aufgaben teilnimmt, die jede Maschine ausführt.

  1. Jede Maschine empfängt N / 100 der Zahlen, berechnet ihren eigenen Median und sendet diese Informationen an den Master.
  2. Der Master erstellt eine sortierte Liste aller unterschiedlichen Mediane und sendet diese an jede Maschine zurück. Dabei wird eine geordnete Folge von Buckets (auf jeder Maschine gleich) definiert, eine für jeden Medianwert (ein Einzelwert-Bucket) und eine für jedes Intervall dazwischen benachbarte Mediane. Natürlich gibt es auch die unteren und oberen Eimer für Werte unterhalb des niedrigsten Medians und oberhalb des höchsten.
  3. Jede Maschine berechnet, wie viele Zahlen in jeden Bucket fallen, und übermittelt diese Informationen an den Master zurück.
  4. Der Master bestimmt, welcher Bucket den Median enthält, wie viele niedrigere Werte (insgesamt) unter diesen Bucket fallen und wie viele darüber.
  5. Wenn der ausgewählte Bucket ein einwertiger Bucket (einer der Mediane) ist oder der ausgewählte Bucket nur 1 (N ungerade) oder 2 (N gerade) Werte enthält, sind wir fertig. Andernfalls wiederholen wir die obigen Schritte mit den folgenden (offensichtlichen) Änderungen:
  6. Nur die Nummern aus dem ausgewählten Bucket werden vom Master (neu) auf die 100 Maschinen verteilt und darüber hinaus
  7. Wir werden nicht (auf jeder Maschine) den Median berechnen, sondern den k-ten Wert, wobei wir berücksichtigen, wie viele höhere Zahlen aus der Summe verworfen wurden und wie viele niedrigere Zahlen. Konzeptionell hat jede Maschine auch ihren Anteil an den verworfenen niedrigen / hohen Zahlen und berücksichtigt dies bei der Berechnung des neuen Medians in der Menge, der (konzeptionell) (seinen Anteil an) den verworfenen Zahlen enthält.

Zeitkomplexität:

  1. Ein wenig Nachdenken wird Sie davon überzeugen, dass bei jedem Schritt die Gesamtzahl der zu analysierenden Werte um einen Faktor von mindestens zwei reduziert wird (2 wäre ein ziemlich kranker Fall; Sie können eine deutlich bessere Reduzierung erwarten). Daraus erhalten wir:
  2. Unter der Annahme, dass das Finden des Medians (oder des k-ten Werts), der O (N) ist, c * N Zeit benötigt, wobei der Präfaktor c nicht zu stark mit N variiert, so dass wir ihn für den Moment als Konstante nehmen können, wir Wir werden unser Endergebnis in höchstens 2 * c * N / 100 Zeit erhalten. Die Verwendung von 100 Maschinen ergibt daher einen Beschleunigungsfaktor von 100/2 (mindestens).
  3. Wie zunächst bemerkt: Die Zeit, die für die Kommunikation der Nummern zwischen den Maschinen benötigt wird, kann es attraktiver machen, einfach alles auf einer Maschine zu erledigen. Wenn wir uns jedoch für den verteilten Ansatz entscheiden, wird die Gesamtzahl der in allen Schritten zusammen zu übermittelnden Zahlen 2 * N nicht überschreiten (N zum ersten Mal, <= N / 2 zum zweiten Mal, <= die Hälfte davon drittens und so weiter).
Bert te Velde
quelle
-1
  1. Teilen Sie die 1 Milliarde Zahlen in 100 Maschinen. Jede Maschine hat 10 ^ 7 Nummern.

  2. Speichern Sie für jede an eine Maschine eingehende Nummer die Nummer in einer Frequenzkarte, Nummer -> Anzahl. Speichern Sie auch die Mindestanzahl in jeder Maschine.

  3. Finden Sie den Median in jeder Maschine: Summieren Sie ausgehend von der Mindestanzahl in jeder Maschine die Anzahl, bis der Medianindex erreicht ist. Der Median in jeder Maschine ist der ca. kleiner und größer als 5 * 10 ^ 6 Zahlen.

  4. Finden Sie den Median aller Mediane, der kleiner und größer als ca. 50 * 10 ^ 7 Zahlen, das ist der Median von 1 Milliarde Zahlen.

Nun einige Optimierung des 2. Schritts: Anstatt in einer Frequenzkarte zu speichern, speichern Sie die Zählwerte in einem Array mit variablen Bits. Zum Beispiel: Nehmen wir an, ab einer Mindestanzahl in einer Maschine sind dies Frequenzzählungen:

[min number] - 8 count
[min+1 number] - 7 count
[min+2 number] - 5 count

Das Obige kann in einem Bit-Array gespeichert werden als:

[min number] - 10000000
[min+1 number] - 1000000
[min+2 number] - 10000

Beachten Sie, dass es insgesamt ungefähr 10 ^ 7 Bits für jede Maschine kostet, da jede Maschine nur 10 ^ 7 Zahlen verarbeitet. 10 ^ 7 Bits = 1,25 * 10 ^ 6 Bytes, was 1,25 MB entspricht

Mit dem obigen Ansatz benötigt jede Maschine 1,25 MB Speicherplatz, um den lokalen Median zu berechnen. Der Median der Mediane kann aus diesen 100 lokalen Medianen berechnet werden, was zu einem Median von 1 Milliarde Zahlen führt.

Shiv
quelle
Was ist, wenn die Zahlen Floats sind?
Sklivvz
-1

Ich schlage eine Methode zur Berechnung des Medians vor. :) Wenn diese eine Milliarde Zahlen in zufälliger Reihenfolge vorliegen, kann ich 1/100 oder 1/10 einer Milliarde zufällig auswählen, sie mit 100 Maschinen sortieren und dann den Median auswählen. Oder lassen Sie uns Milliardenzahlen in 100 Teile aufteilen, jede Maschine 1/10 jedes Teils zufällig auswählen und den Median davon berechnen. Danach haben wir 100 Zahlen und können den Median der 100 Zahlen einfacher berechnen. Nur ein Vorschlag, ich bin mir nicht sicher, ob es mathematisch korrekt ist. Aber ich denke, Sie können das Ergebnis einem nicht so guten Mathe-Manager zeigen.

fauler Junge
quelle
Es ist offensichtlich nicht korrekt, und ich empfehle Ihnen dringend, niemals anzunehmen, dass Ihr Interviewer ein dummes Schwein ist, das Sie
austricksen
Haha ok, aber es ändert nichts an der Tatsache, dass deine Antwort falsch ist. Es ist sehr einfach, es zu beweisen
Dici
OK, nachdem ich einen Vortrag über Statistik gelesen habe, denke ich, dass die Idee, 1/100 oder sogar 1/1000 zufällig von einer Milliarde zu nehmen und ihren Median zu berechnen, nicht so schlecht ist. Es ist nur eine ungefähre Berechnung.
Lazyboy
-3

Steve Jessops Antwort ist falsch:

Betrachten Sie die folgenden vier Gruppen:

{2, 4, 6, 8, 10}

{21, 21, 24, 26, 28}

{12, 14, 30, 32, 34}

{16, 18, 36, 38, 40}

Der Median ist 21, der in der zweiten Gruppe enthalten ist.

Der Median der vier Gruppen beträgt 6, 24, 30, 36, der Gesamtmedian beträgt 27.

Nach der ersten Schleife werden die vier Gruppen zu:

{6, 8, 10}

{24, 26, 28}

{12, 14, 30}

{16, 18, 36}

Die 21 wird bereits fälschlicherweise verworfen.

Dieser Algorithmus unterstützt den Fall nur, wenn zwei Gruppen vorhanden sind.

dunkler Lord
quelle