Tìm một trung gian song song

Question

Nếu bạn có một số lượng lớn các con số và một trăm máy tính, Bạn sẽ tìm thấy số trung vị của các số như thế nào?

Answer 1

Sử dụng thuật toán lựa chọn.

1. Tách mảng số thành 100 phân đoạn.
2. Mỗi bộ xử lý nên sử dụng trục chung để chia mảng hai nhóm (trái/phải)
3. sau đó mỗi bộ xử lý nên gửi kích thước của những 2 nhóm để các nhà lãnh đạo
4. lãnh đạo nên tính toán mà nhóm nhỏ và phát một tin nhắn để thoát khỏi một trong những nhóm đó.
5. quay lại bước 2 cho đến khi bạn tìm ra trung bình

giải pháp này có một thời gian chạy trung bình của O (n) để làm cho nó thời gian chạy tiệm cận của O (n), mỗi bộ xử lý nên chia những con số đối với các nhóm gồm 5 yếu tố, hãy tìm trung vị của mỗi nhóm (sử dụng sắp xếp chèn) và gửi những người trung gian đó trở lại người lãnh đạo, người đứng đầu sẽ chọn trung vị của những người đó (sử dụng cùng một bản ngã) và sẽ là trục

đọc bài viết trên wiki - http://en.wikipedia.org/wiki/Selection_algorithm