Trouver une médiane en parallèle

Question

Si vous avez une énorme quantité de nombres et une centaine d'ordinateurs, Comment trouveriez-vous la médiane des nombres?

Answer 1

Utiliser l'algorithme de sélection.

1. Diviser le tableau de nombre en 100 partitions.
2. Chaque processeur doit utiliser le pivot général pour diviser la matrice en deux groupes (gauche/droite)
3. puis chaque processeur doit envoyer la taille de ces 2 groupes au chef
4. le leader doit calculer à quel groupe est plus petite et diffusé un message pour se débarrasser de l'un de ces groupes.
5. revenir à l'étape 2 jusqu'à ce que vous trouviez la médiane

cette solution a un temps d'exécution avg de O (n) afin de rendre l'exécution asymptotique de O (n), chaque processeur doit diviser le nombre à des groupes de 5 éléments trouver la médiane de chaque groupe (en utilisant le tri de l'insertion) et renvoyer ces médianes au chef, le chef choisira la médiane de ces médianes (en utilisant le même algo) et sera le pivot

lire l'article wiki - http://en.wikipedia.org/wiki/Selection_algorithm