Finden Sie einen Median parallel

Question

Wenn Sie eine große Anzahl von Zahlen und einhundert Computer haben, Wie finden Sie den Median der Zahlen?

Answer 1

Verwenden Sie den Auswahlalgorithmus.

1. Teilen Sie das Zahlenfeld auf 100 Partitionen auf. jeder Prozessor sollte die Größe dieser 2 Gruppen an den Führer
2. Der Leiter sollte berechnen, die Gruppe kleiner senden ist
3. sollte jeder Prozessor die allgemeine Dreh verwenden, um die Anordnung zu zwei Gruppen aufgeteilt (links/rechts)
4. dann und senden Sie eine Nachricht, um von einer dieser Gruppen loszuwerden.
5. geht zurück zu Schritt 2, bis Sie die mittleren

diese Lösung hat eine avg Laufzeit von O (n) um es asymptotische Laufzeit von O (n) zu machen finden, wobei jeder Prozessor der Zahlen aufgeteilt werden soll zu Gruppen von 5 Elementen finden Sie den Median jeder Gruppe (mit Insertion sort) und senden Sie diese Mediane zurück an den Führer, der Führer wird den Median dieser Mediane (mit dem gleichen Algo) und dass wird der Drehpunkt sein

lesen Sie den Wiki-Artikel - http://en.wikipedia.org/wiki/Selection_algorithm