我需要编写一个算法来利用平行锦标赛找到最大值的位置。我有这个代码来寻找最大值:
//共享内存变量n:values M[0..n-1]:带值的数组
//并行过程
torneoMaxParalelo(M,n)
int incr=1;
int grande, temp0, temp1;
while (incr < n)
temp0 ← M[pid];
if (pid + incr < n)
temp1 ← M[pid + incr];
else
temp1 ← -infinite;
grande ← max(temp0, temp1);
M[pid] ← grande;
incr = 2 * incr;
算法需要O(log n)时间。非常感谢。
最佳答案
这是伪代码。
parTournMaxIndex(M, idx, n)
int incr;
Write -infinite (some very
small value) into M[n].
Write pid into idx[pid] and write n into idx[pid+n].
incr = 1;
int idx0, idx1, idxBig;
Key key0, key1;
while (incr < n)
Read idx[pid] into idx0 and read idx[pid+incr] into idx1.
Read M[idx0] into key0 and read M[idx1] into key1.
if (key1 > key0) idxBig = idx1;
else idxBig = idx0;
Write idxBig into idx[pid].
incr = 2 * incr;
关于algorithm - 平行比赛。如何返回数组最大值的位置,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/8273843/