algorithm - computing - parallel programming book

Encuentra una mediana en paralelo

Question

Si tiene una gran cantidad de números y cien computadoras, ¿cómo encontraría la mediana de los números?

Answer 1

Usa el algoritmo de selección.

1. Divida la matriz de número en 100 particiones.
2. Cada procesador debe usar el pivote general para dividir la matriz en dos grupos (izquierda / derecha)
3. entonces cada procesador debe enviar el tamaño de esos 2 grupos al líder
4. el líder debe calcular qué grupo es más pequeño y transmitir un mensaje para deshacerse de uno de esos grupos.
5. vuelve al paso 2 hasta que encuentres la mediana

esta solución tiene un tiempo de ejecución promedio de O (n) para hacer un tiempo de ejecución asintótico de O (n), cada procesador debe dividir los números en grupos de 5 elementos, encontrar la mediana de cada grupo (usar ordenación de inserción) y enviar esas medianas De regreso al líder, el líder elegirá la mediana de esas medianas (usando el mismo algoritmo) y ese será el pivote

lea el artículo de la wiki - http://en.wikipedia.org/wiki/Selection_algorithm