Trova una mediana in parallelo

Question

Se si dispone di una enorme quantità di numeri e di un centinaio di computer, Come sarebbe a trovare la mediana dei numeri?

Answer 1

Utilizzare l'algoritmo di selezione.

1. Split la matrice di numero a 100 partizioni.
2. Ogni processore deve utilizzare il perno generale di suddividere la matrice a due gruppi (sinistra/destra)
3. allora ogni processore dovrebbe inviare le dimensioni di tali 2 gruppi al leader
4. il leader dovrebbe calcolare quale gruppo è più piccolo e trasmettere un messaggio per sbarazzarsi di uno di questi gruppi.
5. tornare al passo 2 fino a trovare la mediana

questa soluzione ha un tempo di esecuzione media di O (n) al fine di rendere più tempo di esecuzione asintotico di O (n), ogni processore dovrebbe dividere i numeri a gruppi di 5 elementi trovare la mediana di ciascun gruppo (mediante inserzione) e inviare tali mediane indietro al leader, il leader sceglierà la mediana di tali mediane (utilizzando la stessa algo) e che sarà il perno

leggi l'articolo wiki - http://en.wikipedia.org/wiki/Selection_algorithm