Clasificación de la lista

En algoritmos paralelos , el problema de clasificación de listas consiste en determinar la posición, o rango, de cada elemento en una lista enlazada . Convencionalmente, este rango indica la distancia de un elemento al final de la lista; por ejemplo, al último elemento se le podría asignar un rango de 0, al penúltimo un rango de 1, y así sucesivamente. Sin embargo, la métrica es genérica y frecuentemente se adapta para calcular la distancia desde el inicio. Si bien es sencillo resolver este problema de manera eficiente en una computadora secuencial, recorriendo la lista en orden, es más complejo resolverlo en paralelo. Como escribieron Anderson y Miller (1990) , el problema se consideró importante en la comunidad de algoritmos paralelos tanto por sus numerosas aplicaciones como porque su resolución condujo a muchas ideas importantes que podían aplicarse a algoritmos paralelos en general.

El problema de la clasificación de listas fue planteado por Wyllie (1979) , quien lo resolvió con un algoritmo paralelo que utilizaba tiempo logarítmico y O( n log n ) pasos totales (es decir, O( n ) procesadores). A lo largo de una serie de artículos posteriores, esto finalmente se mejoró a un número lineal de pasos (O( n /log n ) procesadores), en el modelo más restrictivo de computación paralela síncrona de memoria compartida, la PRAM de lectura exclusiva y escritura exclusiva ( Vishkin 1984 ; Cole y Vishkin 1989 ; Anderson y Miller 1990 ). Este número de pasos coincide con el del algoritmo secuencial.

La clasificación de listas puede considerarse equivalente a realizar una suma de prefijos sobre la lista dada, donde todos los valores a sumar son iguales a uno. El problema de clasificación de listas se puede utilizar para resolver muchos problemas en árboles mediante una técnica de recorrido de Euler , en la que se forma una lista enlazada que incluye dos copias de cada arista del árbol, una en cada dirección, se colocan los nodos de esta lista en una matriz ordenada mediante la clasificación de listas y, a continuación, se realizan cálculos de suma de prefijos sobre la matriz ordenada ( Tarjan y Vishkin, 1985 ) . Por ejemplo, la altura de cada nodo en el árbol se puede calcular mediante un algoritmo de este tipo en el que la suma de prefijos suma 1 por cada arista descendente y resta 1 por cada arista ascendente.

• Anderson, Richard J.; Miller, Gary L. (1990), "Un algoritmo paralelo aleatorio simple para la clasificación de listas", Information Processing Letters , 33 (5): 269– 273, doi : 10.1016/0020-0190(90)90196-5.
• Cole, Richard; Vishkin, Uzi (1989), "Sumas de prefijos paralelas óptimas más rápidas y clasificación de listas", Information and Computation , 81 (3): 334–352 , doi : 10.1016/0890-5401(89)90036-9.
• Tarjan, Robert E .; Vishkin, Uzi (1985), "Un algoritmo eficiente de biconectividad paralela", SIAM Journal on Computing , 14 (4): 862– 874, CiteSeerX 10.1.1.465.8898 , doi : 10.1137/0214061 , S2CID 7231609  .
• Vishkin, Uzi (1984), "Aceleraciones aleatorias en computación paralela", Actas del decimosexto simposio anual de la ACM sobre Teoría de la Computación - STOC '84 , págs. 230–239 , doi : 10.1145/800057.808686 , ISBN  0-89791-133-4, S2CID 17475781 .
• Wyllie, JC (1979), La complejidad de la computación paralela , tesis doctoral, Departamento de Ciencias de la Computación, Universidad de Cornell.