2500335697

Algorytm 5: List Ranking 1: for i — 1 to n in parallel do

2:    Rank[i]=l

3:    Next[i]=Link[i]

4: end for

5: for j — 1 to [lgn\ do 6:    for ?i = 1 to n in parallel do

7:    if Next[i] ^ 0 then

8:    Rank[i]+ = Rank[N ext[i]\

9:    Next[i] = Next[Next[i]\

10:    end if

11:    end for

12: end for

We: Tablice A[ 1 : n], Link[ 1 : ń\.

Wy: Rank[l:n]

Model: EREW PRAM.

Czas O(lgn) i 0(n) procesorów.

Notatki

Na rysunku znajdują się procesory oznaczone prostokątami w kolejności wskazywanej przez Link. Strzałki obrazują wartość Next, a liczby wpisane w każdy prostokąt wartości Rank.

dTt

Notatki

14