Рейтинг списка
В параллельных алгоритмах проблема ранжирования списка включает в себя определение позиции или ранга каждого элемента в связанном списке . То есть первому элементу списка должен быть присвоен номер 1, второму элементу списка должен быть присвоен номер 2 и т. д. Хотя эффективно решить эту проблему на последовательном компьютере несложно, просматривая список в порядка, сложнее решать параллельно. Как писали Андерсон и Миллер (1990) , эта проблема считалась важной в сообществе параллельных алгоритмов как из-за ее многочисленных приложений, так и потому, что ее решение привело ко многим важным идеям, которые можно было применить в параллельных алгоритмах в более широком смысле.
История
[ редактировать ]Проблема ранжирования списка была поставлена Уилли (1979) , который решил ее с помощью параллельного алгоритма, использующего логарифмическое время и общее количество шагов O( n log n ) (то есть процессоров O( n )). В ряде последующих статей это в конечном итоге было усовершенствовано до линейного числа шагов (процессоры O( n /log n )) в наиболее ограничительной модели синхронных параллельных вычислений с общей памятью — PRAM с эксклюзивным чтением и эксклюзивной записью ( Vishkin 1984 ; Коул и Вишкин 1989 ; Андерсон и Миллер 1990 ). Это количество шагов соответствует последовательному алгоритму.
Связанные проблемы
[ редактировать ]Ранжирование списка можно эквивалентно рассматривать как выполнение операции суммирования префиксов в данном списке, в которой все суммируемые значения равны единице. Проблема ранжирования списка может использоваться для решения многих задач о деревьях с помощью метода Эйлера обхода , при котором формируется связный список, включающий две копии каждого ребра дерева, по одной в каждом направлении, и помещаются узлы этого списка в упорядоченный массив, используя ранжирование по списку, а затем выполняет вычисления суммы префиксов для упорядоченного массива ( Тарьян и Вишкин, 1985 ). Например, высота каждого узла в дереве может быть вычислена с помощью алгоритма этого типа, в котором сумма префикса добавляет 1 для каждого нисходящего ребра и вычитает 1 для каждого восходящего ребра.
Ссылки
[ редактировать ]- Андерсон, Ричард Дж.; Миллер, Гэри Л. (1990), «Простой рандомизированный параллельный алгоритм ранжирования списков», Information Processing Letters , 33 (5): 269–273, doi : 10.1016/0020-0190(90)90196-5 .
- Коул, Ричард; Вишкин, Узи (1989), «Быстрые оптимальные суммы параллельных префиксов и ранжирование списков», Information and Computation , 81 (3): 334–352, doi : 10.1016/0890-5401(89)90036-9 .
- Тарьян, Роберт Э .; Вишкин, Узи (1985), «Эффективный параллельный алгоритм двусвязности», SIAM Journal on Computing , 14 (4): 862–874, CiteSeerX 10.1.1.465.8898 , doi : 10.1137/0214061 , S2CID 7231609 .
- Вишкин, Узи (1984), «Рандомизированное ускорение параллельных вычислений», Труды шестнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '84 , стр. 230–239, doi : 10.1145/800057.808686 , ISBN 0-89791-133-4 , S2CID 17475781 .
- Уилли, Дж. К. (1979), Сложность параллельных вычислений , доктор философии. диссертация на факультете компьютерных наук Корнельского университета .