5,337
edits
Parallel Algorithms: Difference between revisions
→Technique: Pointer Jumping
| Line 364: | Line 364: | ||
===Technique: Pointer Jumping=== | ===Technique: Pointer Jumping=== | ||
List Ranking<br> | List Ranking<br> | ||
Input: A dense array A. For each element, we have a node pointing | Input: A dense array A. For each element except first, we have a node pointing its successor in the array.<br> | ||
Each element, except last, is the successor of one element.<br> | |||
''rank(i)=0'' for last, ''rank(i) = rank(next(i)) + 1'' for the rest<br> | |||
The last element we call the "cashier".<br> | |||
Idea: <br> | |||
At iteration 0, node i points to node i+1<br> | |||
At iteration 1, node i points to node i+2<br> | |||
At iteration 2, node i points to node i+4... | |||
<pre> | |||
for i 1 <= i <= n pardo: | |||
if next[i] == NIL then distance[i] = 0 else distance[i] = 1 | |||
for k = 1 to log g: | |||
distance[i] = distance[i] + distance[next[i]] | |||
next[i] = next[next[i]] | |||
</pre> | |||
Correctness: <br> | |||
* Each element will eventually point to the cashier | |||
* Distance will always be correct | |||
** If next[i] = NIL then distance is to the cashier | |||
** Otherwise the distance is <math>2^k</math> | |||
Complexity: <math>O(\log n)</math> time and <math>O(n\log n)</math> work | |||
==Resources== | ==Resources== | ||