classificação List - List ranking
Em algoritmos paralelos , a classificação lista problema envolve a determinação da posição, ou posição, de cada item em uma lista ligada . Ou seja, o primeiro item da lista deve ser atribuído o número 1, o segundo item da lista deve ser atribuído o número 2, etc. Embora seja simples de resolver este problema de forma eficiente em um computador seqüencial, atravessando a lista em ordem, é mais complicado de resolver em paralelo. Como Anderson & Miller (1990) escreveu, o problema foi visto como importante na comunidade algoritmos paralelos, tanto para suas muitas aplicações e por resolvê-lo levado a muitas idéias importantes que poderiam ser aplicadas em algoritmos paralelos de modo mais geral.
História
O problema lista de classificação foi colocada por Wyllie (1979) , que resolveu com um algoritmo paralelo usando o tempo logarítmica e O ( n log n ) passos totais (ou seja, O ( n ) processadores). Ao longo de uma sequência de muitos trabalhos posteriores, este acabou por ser melhorada para linearmente muitos passos (O ( n / log n ) processadores), no modelo mais restritiva de computação paralela de memória compartilhada síncrona, o exclusivo ler exclusivo write PRAM ( Vishkin 1984 ; Cole & Vishkin 1989 ; Anderson & Miller 1990 ). Este número de passos corresponde ao algoritmo sequencial.
problemas relacionados
Classificação lista pode equivalentemente ser visto como executar uma soma prefixo operação na lista dada, em que os valores a serem somados são todos iguais a um. O problema ranking de lista pode ser usada para resolver muitos problemas em árvores através de um passeio de Euler técnica, em que se forma uma lista ligada que inclui duas cópias de cada borda da árvore, uma em cada sentido, coloca os nós desta lista em um matriz ordenada usando classificação lista, e, em seguida, executa cálculos de soma de prefixo na matriz ordenada ( Tarjan & Vishkin 1985 ). Por exemplo, a altura de cada nó da árvore pode ser calculada por um algoritmo deste tipo em que a soma prefixo adiciona uma para cada bordo descendente e subtrai uma para cada aresta ascendente.
Referências
- Anderson, Richard J .; Miller, Gary L. (1990), "Um algoritmo paralelo aleatória simples para a lista de escalão", Information Processing Letters , 33 (5): 269-273, doi : 10,1016 / 0020-0190 (90) 90196-5.
- Cole, Richard; Vishkin, Uzi (1989), "mais rápido óptimas somas prefixo paralelas e lista de ordenação", de informação e de Computação , 81 (3): 334-352, DOI : 10.1016 / 0890-5401 (89) 90036-9.
- Tarjan, Robert E. ; Vishkin, Uzi (1985), "Um algoritmo biconnectivity paralelo eficiente", SIAM Journal na Computing , 14 (4): 862-874, CiteSeerX 10.1.1.465.8898 , doi : 10,1137 / 0214061.
- Vishkin, Uzi (1984), "velocidade-ups randomizados em computação paralela", Annual ACM Symposium on Theory of Computing : 230-239, DOI : 10,1145 / 800.057,808686 , ISBN 0-89791-133-4.
- Wyllie, JC (1979), A complexidade de computação paralela , Ph.D. tese, do Departamento de Ciência da Computação, Universidade de Cornell.