Введение
В параллельных алгоритмах задача ранжирования списка включает определение позиции или ранга каждого элемента в связанном списке. То есть первому пункту в списке следует присвоить номер 1, второму пункту в списке - номер 2 и т.д. Хотя это просто решить эту проблему эффективно на последовательном компьютере, пересекая список в порядке, это более сложно решить параллельно. Как написано, проблема рассматривалась как важная в сообществе параллельных алгоритмов как для ее многочисленных применений, так и потому, что ее решение привело к многим важным идеям, которые можно было бы применить в параллельных алгоритмах в более общем смысле.
История
Проблема ранжирования списков была поставлена , который решил ее с помощью параллельного алгоритма, используя логарифмическое время и O ((n log n) общих шагов (то есть O ((n) процессоров). В течение последовательности многих последующих статей, это было в конечном итоге улучшено до линейно многоступенчатых (O ((n / log n) процессоров), на самой ограничительной модели синхронной параллельной вычисления совместной памяти, эксклюзивной читать эксклюзивный писать PRAM (; ;). Это число шагов соответствует последовательному алгоритму.
Связанные проблемы
Рейтинг списка может быть рассматривается как выполнение операции суммирования префикса в данном списке, в которой суммируемые значения равны одному. Проблема ранжирования списков может быть использована для решения многих задач на деревьях с помощью техники Эулеровского тура, в которой формируется связанный список, который включает две копии каждого края дерева, по одной в каждом направлении, помещает узлы этого списка в упорядоченный массив с использованием ранжирования списков, а затем выполняет вычисления суммы префикса на упорядоченном массиве. Например, высота каждого узла в дереве может быть вычислена алгоритмом такого типа, в котором сумма префикса добавляет 1 для каждого нисходящего края и вычитает 1 для каждого восходящего края.