我需要编写一个算法来利用平行锦标赛找到最大值的位置。我有这个代码来寻找最大值:
//共享内存变量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/

10-13 01:21